深度优先搜索使用的策略是,只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索,知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了,搜索就回溯到v的前驱结点(v是经该结点才被发现的),来搜索该前驱结点的出发边。该过程持续知道从源结点可以到达的所有结点都被发现为止。此后若还存在未被发现的结点,则DFS将从从未被发现的结点中任选一个结点作为新的源节点,并重复同样的过程。
还是老办法,上代码,可以清楚地解释:
1 #include <iostream> 2 #include <list> 3 using namespace std; 4 5 class Graph{ 6 private: 7 int v;//结点数 8 list<int>* adj;//结点临接链表 9 void DFSUtil(int u,bool visited[]); 10 public: 11 Graph(int v); 12 void addEdge(int start,int end); 13 void DFS(); 14 }; 15 16 Graph::Graph(int v){ 17 this->v = v; 18 adj = new list<int>[v]; 19 } 20 21 //无向图 22 void Graph::addEdge(int start,int end){ 23 adj[start].push_back(end); 24 adj[end].push_back(start); 25 } 26 27 void Graph::DFSUtil(int u,bool visited[]){ 28 visited[u] = true; 29 cout<<u<<" "; 30 list<int>::iterator beg = adj[u].begin(); 31 for (;beg != adj[u].end();++beg){ 32 if (visited[*beg] == false) 33 DFSUtil(*beg,visited); 34 } 35 } 36 37 void Graph::DFS(){ 38 bool* visited = new bool[v]; 39 for (int i=0;i<v;i++) 40 visited[i] = false; 41 //递归调用dfsutil函数深度遍历每个结点 42 for (int i=0;i<v;i++) 43 if (visited[i] == false) 44 DFSUtil(i,visited); 45 cout<<endl; 46 } 47 48 int main() 49 { 50 Graph g = Graph(8); 51 g.addEdge(0,1); 52 g.addEdge(0,2); 53 g.addEdge(0,5); 54 g.addEdge(1,3); 55 g.addEdge(2,3); 56 g.addEdge(2,4); 57 g.addEdge(2,5); 58 g.addEdge(4,5); 59 g.addEdge(6,7); 60 g.DFS(); 61 62 return 0; 63 }
需要指出的是,本例使用的是无向图,但DFS也可以针对有向图。
需要加以说明的是,即使该图中有结点无法保证能到达图中所有结点,但代码中第42行可以保证图中每个结点都会被访问到。
运行结果如下:
文献引用:算法导论->22章->基本图算法
代码参考:http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/