大家好,今天我们来学习深度优先搜索(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号卡片。以此类推下去,相信大家已经看懂了。

下面我们代码实现!


下面的代码可以解决不超过10个数的全排列的问题。(当然你可以改变数组大小)

#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

成功~


作者:ChungZH

审稿:未央