深度优先搜索 (Depth first search)浅析 - 算法笔记

其实也不难

Posted by ChungZH on 2018-10-13

大家好,今天我们来学习深度优先搜索(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个数的全排列的问题。(当然你可以改变数组大小)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}

输入:

1
3

输出:

1
2
3
4
5
6
123
132
213
231
312
321

成功~


作者:ChungZH

审稿:未央