深度優(yōu)先搜索使用的策略是，只要與可能就在圖中盡量“深入”。DFS總是對(duì)最近才發(fā)現(xiàn)的結(jié)點(diǎn)v出發(fā)邊進(jìn)行探索，知道該結(jié)點(diǎn)的所有出發(fā)邊都被發(fā)現(xiàn)為止。一旦v的所有出發(fā)邊都被發(fā)現(xiàn)了，搜索就回溯到v的前驅(qū)結(jié)點(diǎn)（v是經(jīng)該結(jié)點(diǎn)才被發(fā)現(xiàn)的），來(lái)搜索該前驅(qū)結(jié)點(diǎn)的出發(fā)邊。該過(guò)程持續(xù)知道從源結(jié)點(diǎn)可以到達(dá)的所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。此后若還存在未被發(fā)現(xiàn)的結(jié)點(diǎn)，則DFS將從從未被發(fā)現(xiàn)的結(jié)點(diǎn)中任選一個(gè)結(jié)點(diǎn)作為新的源節(jié)點(diǎn)，并重復(fù)同樣的過(guò)程。

　　還是老辦法，上代碼，可以清楚地解釋：

1 #include <iostream> 2 #include <list> 3 using namespace std; 4 5 class Graph{ 6 private: 7 int v;//結(jié)點(diǎn)數(shù) 8 list<int>* adj;//結(jié)點(diǎn)臨接鏈表 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 //無(wú)向圖 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 //遞歸調(diào)用dfsutil函數(shù)深度遍歷每個(gè)結(jié)點(diǎn) 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 }

需要指出的是，本例使用的是無(wú)向圖，但DFS也可以針對(duì)有向圖。

需要加以說(shuō)明的是，即使該圖中有結(jié)點(diǎn)無(wú)法保證能到達(dá)圖中所有結(jié)點(diǎn)，但代碼中第42行可以保證圖中每個(gè)結(jié)點(diǎn)都會(huì)被訪問(wèn)到。

運(yùn)行結(jié)果如下：

文獻(xiàn)引用：算法導(dǎo)論->22章->基本圖算法

代碼參考：http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

轉(zhuǎn)載于:https://www.cnblogs.com/lxiao/p/4320601.html

總結(jié)

以上是生活随笔為你收集整理的算法系列之图--DFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。