转载

算法系列之图--DFS

深度优先搜索使用的策略是,只要与可能就在图中尽量“深入”。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行可以保证图中每个结点都会被访问到。

运行结果如下:

算法系列之图--DFS

文献引用:算法导论->22章->基本图算法

代码参考:http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

正文到此结束
Loading...