本文實例講述了圖的遍歷中深度優先搜索的C++實現方法，是一種非常重要的算法，具體實現方法如下：
首先，圖的遍歷是指從圖中的某一個頂點出發，按照某種搜索方法沿著圖中的邊對圖中的所有頂點訪問一次且僅訪問一次。注意到樹是一種特殊的圖，所以樹的遍歷實際上也可以看作是一種特殊的圖的遍歷。圖的遍歷主要有兩種算法：廣度優先搜索（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
|
/************************************************************************* > File Name: DFS.cpp > Author: SongLee ************************************************************************/#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)。
