这篇文章讲解一下 深度优先搜索(DFS)


前言

深度优先搜索(Depth first search, DFS)算法是一种搜索算法。

深度优先搜索

首先,我们做一道小学奥数题。

Q:用 1、2、3 三个数 能组成多少个三位数?请把组成的三位数写出来。(不能重复使用同一个数)

**A: ​ 答:能组成6个三位数,分别是: ​ 123 ​ 132 ​ 213 ​ 231 ​ 312 ​ 321 **

现在,就让我用深度优先搜索的思想来解决这个小学奥数题吧!(呕吐)

简化后的问题是:我们把每一位数看成一个盒子,把 1、2、3 看成三张卡片。现在把这三张卡片分别放进三个盒子里面,而且每个盒子里只能放一个扑克牌。问有多少种放法?

首先在 A 盒子面前,放进了 1 号卡片。然后走到 B 个盒子面前,放进了 2 号卡片。然后走到 C 盒子面前,放进了 3 号卡片。这时,就形成了一种放法:123。

卡片都放完了,但是放法可不止这种。怎么办呢?这时我就要收回第三张卡片,往回走到 B 盒子面前。但是,我手里还是只有 3 号卡片,还是只能放 3 号卡片到 C 盒子里。所以,现在我就要收回在 B 盒子里的 2 号卡片,再往回走到A盒子。好了,现在我手里有 2 号卡片和 3 号卡片。现在我们走到B盒子,由于上次在 B 盒子里放了 2 号卡片。这次我要放 3 号卡片进 B 盒子。然后,就把 2 号卡片放进 C 盒子,这样又形成了一种方法:132。

好了,这次我们就要一直后退到 A 盒子,把三张卡片都收回,然后往 A 盒子放进 2 号卡片。以此类推下去。


#include <iostream>
using namespace std;

int a[10], book[10], n;
        // book数组用来标记这张卡片是否已经不在手中

void dfs(int step);  // step 代表现在在哪个盒子面前

int main()
{
	cin >> n;
	dfs(1);   // 开始dfs搜索

	return 0;
}

void dfs(int step)
{
	if (step == n+1) // 在 n + 1 个盒子面前(即放完卡片)
	{
		// 输出一种放法
		for (int i = 1; i <= n; i++)
		{
			cout << a[i]; 
		}
		cout << endl;

		return;          // 返回到上一步
	}

	for (int i = 1; i <= n; i++)
	{
		// 判断卡片 i 是否还在手上
		if (book[i] == 0)  //
		{
			a[step] = i;  // 将i号卡片放入到第step个盒子中
			book[i] = 1;  // 表示i号卡片已经不在手上,放进盒子里了
			dfs(step+1);  // 递归调用
			book[i] = 0;  // 将刚刚放进盒子里的卡片拿回来,才能进行下一步搜索
		}

		
	}
	return;
}

输入:

3

输出:

123
132
213
231
312
321