深度优先搜索的实现

发表于   |   分类于   |  

图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历主要有两种算法：广度优先搜索（Breadth-First-Search）和深度优先搜索（Depth-First-Search）。

深度优先搜索（DFS）的算法思想

深度优先搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想就是：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。

如上图所示，从顶点2开始深度优先遍历图，结果为：2，0，1，3。

DFS算法实现

和广度优先搜索一样，为了防止顶点被多次访问，需要使用一个访问标记数组visited[]来标记顶点是否已经被访问过。

这里使用邻接表表示图。对于一个有向图，假设从给定顶点可以访问到图的所有其他顶点，则DFS递归算法的C++代码实现：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*************************************************************************
    > File Name: DFS.cpp
    > Author: SongLee
    > E-mail: lisong.shine@qq.com
    > Created Time: 2014年07月04日 星期五 10时38分26秒
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#include<iostream>
#include<list>
using namespace std;

/* 图 */
class Graph
{
	int V;                               // 顶点数
	list<int> *adj;                      // 邻接表
	void DFSUtil(int v, bool visited[]); // 从顶点v深度优先遍历
public:
	Graph(int V);                        // 构造函数
	void addEdge(int v, int w);          // 向图中添加边
	void DFS(int v);                     // 从v开始深度优先遍历图
};

/* 构造函数 */
Graph::Graph(int V)
{
	this->V = V;
	adj = new list<int>[V];
}

/* 添加边，构造邻接表 */
void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);                 // 将w添加到v的链表
}

/* 从v开始深度优先遍历 */
void Graph::DFSUtil(int v, bool visited[])
{
	// 访问顶点v并输出
	visited[v] = true;
	cout << v << " ";

	list<int>::iterator i;

	for(i=adj[v].begin(); i!=adj[v].end(); ++i)
		if(!visited[*i])              // 若邻接点尚未访问
			DFSUtil(*i, visited);     // 递归
}

/* 对图进行深度优先遍历，调用递归函数DFSUtil() */
void Graph::DFS(int v)
{
	bool *visited = new bool[V];
	for(int i=0; i<V; ++i)
		visited[i] = false;

	// 假设从给定顶点v可以到达图的所有顶点
	DFSUtil(v, visited);
}

/* 测试 */
int main()
{
	Graph g(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);

	cout << "Depth First Traversal (starting from vertex 2) \n";
	g.DFS(2);
	cout << endl;
	
	return 0;
}

上面的代码是假设从给定顶点可以访问到图的所有其他顶点。如果没有这个假设，为了对图作一个完整的深度优先遍历，我们需要对每个顶点调用DFSUtil()。当然那之前需要先检查顶点是否已经访问过。所以我们只需要修改DFS()函数部分：

1
2
3
4
5
6
7
8
9
10
11
void Graph::DFS()
{
	bool *visited = new bool[V];
	for(int i=0; i<V; ++i)
		visited[i] = false;
	
	// 对每个顶点调用DFSUtil()，从0开始
	for(int i=0; i<V; ++i)
		if(!visited[i])
			DFSUtil(i, visited);
}

对于无向图的深度优先搜索，只是邻接表不一样，其他的都是一样的。我们只需要修改addEdge(v, w)函数：

1
2
3
4
5
void Graph::addEdge(int v, int w)
{
  adj[v].push_back(w);         // 将w加到v的list
  adj[w].push_back(v);
}

注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，如果边的输入次序不同，生成的邻接表也不同。因此，对于同一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

DFS算法性能分析

1 . 空间复杂度

DFS算法是一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为O(|V|)。

2 . 时间复杂度

  • 当以邻接表存储时，时间复杂度为O(|V|+|E|)。

  • 当以邻接矩阵存储时，时间复杂度为O(|V|^2)。