欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

啊哈算法之深度优先搜索(Depth First Search,DFS)

程序员文章站 2022-05-22 20:57:07
...

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。比如我们这里写的dfs(step)函数的主要功能就是解决当你在第step个盒子的时候该怎么办。通常的方法就是把每一种可能都去尝试一遍(一般使用for循环来遍历)。当前这一步解决后便进入下一步dfs(step+1).

下面代码就是深度优先搜索的基本模型:

void dfs(int step)
{
    判断边界
    尝试每一种可能for(i=1;i<=n;i++)
    {
        继续下一步dfs(step+1);
    }
    返回;
}

下面这段代码是前面暴力枚举中例题的另一种解法:

#include <stdio.h>
#include <iostream>

int a[10], book[10], n=9, total;

void dfs(int step)
{
	int i;
	if (step == n + 1)
	{
		if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9])
		{
			total++;
			printf("%d%d%d+%d%d%d = %d%d%d\n", a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]);
		}
		return ;
	}

	for (i = 1; i <= n; i++)
	{
		if (book[i] == 0)
		{
			a[step] = i;
			book[i] = 1;
			dfs(step + 1);
			book[i] = 0;
		}

	}
	//return ;
}

int main()
{
	dfs(1);
	printf("total = %d\n", total / 2);

	system("pause");
	return 0;
}