深度優先搜尋（DFS）思路及演算法分析
摘要：
1、演算法用途：
用於遍歷圖中的節點，有些 類似於 樹的深度優先遍歷 。這裡唯一的問題是，與樹不同，圖形可能包含迴圈，因此我們可能會再次來到同一節點。
2、主要思想：
借用一個鄰接表和布林型別陣列（判斷一個點是否檢視過，用於避免重複到達同一個點，造成死迴圈等），...
1、演算法用途：
用於遍歷圖中的節點，有些 類似於 樹的深度優先遍歷 。這裡唯一的問題是，與樹不同，圖形可能包含迴圈，因此我們可能會再次來到同一節點。
2、主要思想：
借用一個鄰接表和布林型別陣列（判斷一個點是否檢視過，用於避免重複到達同一個點，造成死迴圈等），先將所有點按一定次序存入鄰接表，再通過迭代器，對鄰接表的linklist和布林陣列做出操作，從而達到不重複遞迴遍歷的效果。
（鄰接表是表示了圖中與每一個頂點相鄰的邊集的集合，這裡的集合指的是無序集）
3、 程式碼（java）：
(以上圖為例的程式碼）
1 //深度優先搜尋
2 import java.io.*;
3 import java.util.*;
4
5 //This class represents a directed graph using adjacency list
6 //representation
7 class Graph
8 {
9private int V; // No. of vertices
10
11// Array of lists for Adjacency List Representation
12private LinkedList<Integer> adj[];
13
14// Constructor
15Graph(int v)
16{
17V = v;
18adj = new LinkedList[v];
19for (int i=0; i<v; ++i)
20adj[i] = new LinkedList();
21}
22
23//Function to add an edge into the graph
24void addEdge(int v, int w)
25{
26adj[v].add(w); // Add w to v's list.
27}
28
29// A function used by DFS
30void DFSUtil(int v,boolean visited[])
31{
32// Mark the current node as visited and print it
33visited[v] = true;
34System.out.print(v+" ");
35
36// Recur for all the vertices adjacent to this vertex
37Iterator<Integer> i = adj[v].listIterator();
38while (i.hasNext())
39{
40int n = i.next();
41if (!visited[n])
42DFSUtil(n,visited);
43}
44}
45
46// The function to do DFS traversal. It uses recursive DFSUtil()
47void DFS()
48{
49// Mark all the vertices as not visited(set as
50// false by default in java)
51boolean visited[] = new boolean[V];
52
53// Call the recursive helper function to print DFS traversal
54// starting from all vertices one by one
55for (int i=0; i<V; ++i)
56if (visited[i] == false)
57DFSUtil(i, visited);
58}
59
60public static void main(String args[])
61{
62Graph g = new Graph(4);
63
64g.addEdge(0, 1);
65g.addEdge(0, 2);
66g.addEdge(1, 2);
67g.addEdge(2, 0);
68g.addEdge(2, 3);
69g.addEdge(3, 3);
70
71System.out.println("Following is Depth First Traversal");
72
73g.DFS();
74}
75 }
4、複雜度分析：
DFS複雜度分析 DFS演算法是一一個遞迴演算法，需要藉助一個遞迴工作棧，故它的空問複雜度為O(V）。 遍歷圖的過程實質上是對每個頂點查詢其鄰接點的過程，其耗費的時間取決於所採用結構。 鄰接表表示時，查詢所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間複雜度為O(V+E)。