DFS（深度优先搜索）的递归与非递归_dfs非递归

DFS，depth-first search，深度优先搜索。顾名思义，从一个节点出发，尽可能往下遍历，即尽可能离“家”远一点，这个思想其实就是树结构遍历中的先序遍历。

那么从上述话语中，我们可以很容易地判断出需要用到递归，其实DFS的常规构造方法也就是用到递归的，但是我们还要考虑到一个问题，那么就是如果一个图足够大，比如有上万个节点，上万条边，那么估计用递归运行DFS我们的电脑会瞬间卡死。。。因为递归的代价实在是太大了，图如果小一点还好，不是特别明显，一旦图过大，递归的劣势会被无限放大，因此这里除了用递归来构造DFS以外，我还会介绍非递归的方法，即通过使用数据结构——栈来代替函数调用，虽说栈的出现会导致占用过多的内存空间，但是，时代变了！区区一个栈再大能够有多大呢？再宝贵能有时间宝贵吗？所以在大型的图深度遍历中，使用栈的DFS绝对要比使用递归的DFS的效率要高！

递归算法转化为非递归算法的优点：

1. 节省内存空间
2. 提高执行效率

一些特殊情况

首先我们需要考虑到一些特殊情况：

• 某些图存在环路，因此我们需要避免因为环路导致的死循环，即重复遍历相同的节点。
  • 解决方案就是，添加一个标志位mark，未遍历的节点mark为0
• 某些图并不是所有的节点都连接在一起，即从一个节点出发可能无法遍历所有的节点。
  • 解决方案就是，在一次遍历结束时，检查标志数组mark[]，通过查看其所有的mark是否为0，来判断是否遍历完所有的节点。

解决完这些特殊情况之后，那么接下来就进入到了正式环节：

常规版本——递归DFS

先上伪代码

因为伪代码没有其他语言的语法限制，能够有助于我们更好地将注意力放在算法上，所以我们先用伪代码来讲述一下主要思想：

algorithm DFS(G)
//实现给定图G的广度优先搜索
//输入：图G=<V, E>，其中V为G中所有的节点集合，E为G中所有的边集合
//输出：图G的节点，按照DFS遍历访问到的先后顺序
count <- 0
for 每个属于V的v do
	mark[v] <- 0  //将每个节点的标志位都赋初值为0，表示未被访问
for 每个属于V的v do
	if mark[v] = 0
		dfsVisit(v)
		
dfsVisit(v)
count <- count + 1
visit(v)
mark[v] <- count
for 每个与v相邻的节点w do
	if mark[w] = 0
		dfsVisit(w)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

由以上代码便实现了DFS，接下来只需要使用某一种特定的高级语言来实现即可。

在实现之前，我们先来探讨一下其中的一些细节：

1.以上代码是否实现了遍历所有节点的要求呢？

首先在DFS()中，我们在调用dfsVisit()函数之前，是用了一个循环遍历所有的节点，然后若一个节点未被遍历，则会调用dfsVisit()函数，随后将与其相连接的节点全部遍历完，因此能够实现遍历所有的节点。

for 每个属于V的v do
	if mark[v] = 0
		dfsVisit(v)
1
2
3

2.以上的代码是否避免了重复遍历相同的节点呢？

在dfsVisit()函数中，遍历队头元素的相邻节点时，首先会判断该节点对应的mark是否为0，即是否未被访问过，若是则将其入队，若已经被访问过了，则跳过，因此能够避免重复遍历。

for 每个与v相邻的节点w do
	if mark[w] = 0
		dfsVisit(w)
1
2
3

3.DFS的最主要步骤就是“回溯”，那么代码中哪里体现了这一点呢？

由于是递归调用实现的，因此其中的“回溯”显得比较隐秘：

for 每个与v相邻的节点w do
	if mark[w] = 0
		dfsVisit(w)
1
2
3

如上所示，其中的“回溯”就体现在递归调用dfsVisit()函数这里，当一直递归到无法再继续递归下去的时候，函数结束，就回到了上一个dfsVisit()函数中，由于其在一个循环中，因此会继续找到下一个与v相邻的节点w，若w依旧未被访问过，则调用dfsVisit()函数，因此“回溯”就体现出来了。

实例

以下图为例

默认起点为S，然后运用DFS遍历整个图，则节点的访问顺序为：SABEDCFGH

因为首先访问S后，会有两个相邻节点，A和C，按照字母表的顺序，优先访问A，之后A的相邻节点有S、B、D，优先访问B，B的相邻节点有A和E，但是由于A已经被访问过，所以访问E，以此类推。

代码实现

理论讲完之后，接下来就是实践了，这里我通过C++来实现BFS。

首先根据上图构造相对应的邻接矩阵，以及初始化mark[]数组：

int Matrix[9][9] = {
	{1, 1, 0, 1, 0, 0, 0, 0, 0},
	{1, 1, 1, 0, 1, 0, 0, 0, 0},
	{0, 1, 1, 0, 0, 1, 0, 0, 0},
	{1, 0, 0, 1, 1, 0, 1, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 1, 0},
	{0, 0, 1, 0, 1, 1, 0, 0, 1},
	{0, 0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 0, 0, 1, 0, 1, 1, 1},
	{0, 0, 0, 0, 0, 1, 0, 1, 1}
};  //这里我将SABCDEFGH依次定义为012345678，因此DFS遍历之后的结果应该为012543678
int mark[9] = { 0 };
1
2
3
4
5
6
7
8
9
10
11
12

然后构造DFS函数：

void dfsVisit(int v) {
	cout << v << endl;
	mark[v] = 1;
	for (int i = 0; i < 9; i++) {
		if (Matrix[i][v] == 1 && mark[i] == 0)
			dfsVisit(i);
	}
}

void DFS() {
	for (int i = 0; i < 9; i++) {
		if (mark[i] == 0)
			dfsVisit(i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

然后在main()函数中调用DFS()：

int main() {
	DFS();
	return 0;
}
1
2
3
4

运行结果为：

进阶版本——非递归DFS

版本一

先上伪代码

还是一样，先来看看伪代码：

algorithm DFS(G)
//实现给定图G的广度优先搜索
//输入：图G=<V, E>，其中V为G中所有的节点集合，E为G中所有的边集合
//输出：图G的节点，按照DFS遍历访问到的先后顺序
count <- 0
for 每个属于V的v do
	mark[v] <- 0  //将每个节点的标志位都赋初值为0，表示未被访问
for 每个属于V的v do
	if mark[v] = 0
		dfsVisit(v)
		
dfsVisit(v)
initialize(S)  //初始化栈S
push(S, v)  //将节点v压入栈中
while 栈S不为空 do
	x <- pop(S)
	push(S, x)  //可以看到这里有一个关键的步骤，弹出栈顶节点之后，又马上将其入栈了
	if mark[x] = 0
		visit(x)
		count <- count + 1
		mark[x] <- count
	if 存在与节点x相邻的节点w and mark[w] = 0
		push(S, w)
	else 
		pop(S)
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

那么我们来探讨一下其中的细节：

1.为什么节点v一开始入栈前不访问，而是在while循环中弹出的时候再访问呢？

假设入栈前访问，那么同样以之前的图为例，则程序运行的过程如下图所示（其中，由于栈结构“后进先出”的特性，以起点S为例，为例确保下次访问的对象为A，则需要先将C入栈，再将A入栈）：

那么节点的入栈顺序为SCADBEHGF，出栈顺序为SABEHGFDC，访问顺序为SCADBEHGF

可以看到，一开始的访问顺序还是正确的，但是到了后面就出现了错误，虽然都是将节点遍历完了，但是其中的思想却与DFS得出的遍历顺序不一样了，因此入栈前访问并不是真正的DFS。

2.在弹出栈中的一个节点的时候，为什么又要马上放进栈中？

和上一个问题一样，出栈后马上入栈的目的一个是为了保证能够将一个节点所有的相邻节点都遍历过，另一个就是为了保证得到一个正确的遍历顺序，那么该伪代码的运行过程为：

可以看到节点入栈的顺序和访问的顺序符合DFS的思想，因此该遍历过程才是正确的。

同时我们要注意的是，因为如果栈顶节点还有相邻的节点未被访问过，则栈顶节点会一直保留，如上图的S、A、B等节点，都一直保留到了最后，因此DFS中的最重要的思想——“回溯”就很明显地体现了出来（递归版本的“回溯”是隐含的），就是如下代码：

if 存在与节点x相邻的节点w and mark[w] = 0
	push(S, w)
else 
	pop(S)
1
2
3
4

即上述if语句判断体现了“回溯”。

代码实现

同样的，这里我还是用C++来实现该算法（因为图还是用的前面的那个，所以这里只给出了实现DFS的部分）：

void dfsVisit(int v) {
	stack <int> S;  //这里使用C++自带的栈结构，需要导入<stack>库
	S.push(v);
	int x;
	while (!S.empty()) {
		x = S.top();
		S.pop();
		S.push(x);
		if (mark[x] == 0) {
			cout << x << endl;
			mark[x] = 1;
		}
		bool find = false;
		for (int i = 0; i < 9; i++) {
			if (Matrix[i][x] == 1 && mark[i] == 0) {
				S.push(i);  //只需要找到一个相邻的且未被访问过的节点
				find = true;
				break;
			}
		}
		if (!find) S.pop();  //若栈顶的节点无相邻且未被访问过的节点，则将其弹出
	}
}

void DFS() {
	for (int i = 0; i < 9; i++) {
		if (mark[i] == 0)
			dfsVisit(i);
	}
}
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

运行结果如下：

可以看到，运行结果和前面的常规版本是一致的。

版本二

前面版本一的一个比较难懂的地方就在于，将栈顶节点弹出栈后，又将其入栈，这也是它的一个特点，那么再来讲讲将栈顶节点弹出栈后不将其入栈的版本。

先上伪代码

algorithm DFS(G)
//实现给定图G的广度优先搜索
//输入：图G=<V, E>，其中V为G中所有的节点集合，E为G中所有的边集合
//输出：图G的节点，按照DFS遍历访问到的先后顺序
count <- 0
for 每个属于V的v do
	mark[v] <- 0  //将每个节点的标志位都赋初值为0，表示未被访问
for 每个属于V的v do
	if mark[v] = 0
		dfsVisit(v)
		
dfsVisit(v)
initialize(S)  //初始化栈S
push(S, v)  //将节点v压入栈中
while 栈S不为空 do
	x <- pop(S)
	if mark[x] = 0
		visit(x)
		count <- count + 1
		mark[x] <- count
		for 所有与节点x相邻的节点w do  //注意：这里必须逆序遍历，否则访问顺序就会出问题
			if mark[w] = 0
				push(S, w)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

首先我们要注意到版本二与版本一的区别：版本一遍历栈顶节点的相邻节点的时候，只需要找到一个入栈就行了，所以是顺序遍历；而版本二则是一次将栈顶节点的所有相邻且未被访问过的节点都入栈，由于栈结构的特性，所以需要逆序遍历，这样才能保证访问顺序是正确的。

如下图为版本二程序运行的过程（依旧以前面的图为例）：

同时我们也要注意到另一个问题，即栈中会有重复的节点存在，如上图中的G，栈中就出现了两个，因此就会导致栈空间不断扩大，所以此算法所需的栈空间会非常庞大，但对于目前最低配置都是256G内存的电脑来说，这点内存空间还真就不足一提，所以其实问题也还是不大，更关键的是非递归算法所花费的时间会远远小于递归算法。

代码实现

同理，依旧用C++来实现：

void dfsVisit(int v) {
	stack <int> S;  //这里使用C++自带的栈结构，需要导入<stack>库
	S.push(v);
	int x;
	while (!S.empty()) {
		x = S.top();
		S.pop();
		if (mark[x] == 0) {
			cout << x << endl;
			mark[x] = 1;
			for (int i = 8; i >= 0; i--) {  //这里必须逆序遍历
				if (Matrix[i][x] == 1 && mark[i] == 0) {
					S.push(i);
				}
			}
		}
	}
}

void DFS() {
	for (int i = 0; i < 9; i++) {
		if (mark[i] == 0)
			dfsVisit(i);
	}
}
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

运行结果如下：

可以看到，运行结果和前面的常规版本是一致的。

效率分析

时间复杂度取决于图的存储方式，若是采用邻接矩阵，则时间复杂度为O(|V|²)；若是采用邻接链表，则时间复杂度为O(|V|+|E|)

DFS的应用

1.检查图的连通性

从任意节点出发，按照DFS遍历，若一次遍历结束后，所有节点的mark标志位都不为0，则说明该图是连通的，否则不连通。

2.检查图的无环性

在用DFS遍历过程中，若发现从一个节点到它的祖父节点有一条回边（即该节点除了从父节点那个方向到它的祖父节点之外，还可以走另一条路到它的祖父节点），则说明该图存在回路，否则该图无回路。

3.求出一个图的割点

割点：图中去掉该点，则剩下的部分会分成若干个不连通的子图，则该点为割点。

4.生成迷宫

可以用DFS在一个区域中进行随机的遍历，然后记录运行轨迹就可以得到一个迷宫

参考资料

《算法设计与分析基础》第三版以及老师的课件