算法系列之图--DFS

  深度优先搜索使用的策略是,只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索,知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了,搜索就回溯到v的前驱结点(v是经该结点才被发现的),来搜索该前驱结点的出发边。该过程持续知道从源结点可以到达的所有结点都被发现为止。此后若还存在未被发现的结点,则DFS将从从未被发现的结点中任选一个结点作为新的源节点,并重复同样的过程。

  还是老办法,上代码,可以清楚地解释:

 #include <iostream>
#include <list>
using namespace std; class Graph{
private:
int v;//结点数
list<int>* adj;//结点临接链表
void DFSUtil(int u,bool visited[]);
public:
Graph(int v);
void addEdge(int start,int end);
void DFS();
}; Graph::Graph(int v){
this->v = v;
adj = new list<int>[v];
} //无向图
void Graph::addEdge(int start,int end){
adj[start].push_back(end);
adj[end].push_back(start);
} void Graph::DFSUtil(int u,bool visited[]){
visited[u] = true;
cout<<u<<" ";
list<int>::iterator beg = adj[u].begin();
for (;beg != adj[u].end();++beg){
if (visited[*beg] == false)
DFSUtil(*beg,visited);
}
} void Graph::DFS(){
bool* visited = new bool[v];
for (int i=;i<v;i++)
visited[i] = false;
//递归调用dfsutil函数深度遍历每个结点
for (int i=;i<v;i++)
if (visited[i] == false)
DFSUtil(i,visited);
cout<<endl;
} int main()
{
Graph g = Graph();
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.addEdge(,);
g.DFS(); return ;
}

需要指出的是,本例使用的是无向图,但DFS也可以针对有向图。

需要加以说明的是,即使该图中有结点无法保证能到达图中所有结点,但代码中第42行可以保证图中每个结点都会被访问到。

运行结果如下:

算法系列之图--DFS

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

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

上一篇:web项目启动首页能访问接口报404


下一篇:userAgent收集