首页 / 算法 / 算法系列之图--DFS
算法系列之图--DFS
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法系列之图--DFS，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1654字，纯文字阅读大概需要3分钟。
内容图文
深度优先搜索使用的策略是，只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索，知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了，搜索就回溯到v的前驱结点（v是经该结点才被发现的），来搜索该前驱结点的出发边。该过程持续知道从源结点可以到达的所有结点都被发现为止。此后若还存在未被发现的结点，则DFS将从从未被发现的结点中任选一个结点作为新的源节点，并重复同样的过程。
还是老办法，上代码，可以清楚地解释：
1 #include <iostream>
2 #include <list>
3usingnamespace std;
4 5class Graph{
6private:
7int v;//结点数 8 list<int>* adj;//结点临接链表 9void DFSUtil(int u,bool visited[]);
10public:
11 Graph(int v);
12void addEdge(int start,int end);
13void DFS();
14};
1516 Graph::Graph(int v){
17this->v = v;
18 adj = new list<int>[v];
19}
2021//无向图22void Graph::addEdge(int start,int end){
23 adj[start].push_back(end);
24 adj[end].push_back(start);
25}
2627void Graph::DFSUtil(int u,bool visited[]){
28 visited[u] = true;
29 cout<<u<<"";
30 list<int>::iterator beg = adj[u].begin();
31for (;beg != adj[u].end();++beg){
32if (visited[*beg] == false)
33 DFSUtil(*beg,visited);
34 }
35}
3637void Graph::DFS(){
38bool* visited = newbool[v];
39for (int i=0;i<v;i++)
40 visited[i] = false;
41//递归调用dfsutil函数深度遍历每个结点42for (int i=0;i<v;i++)
43if (visited[i] == false)
44 DFSUtil(i,visited);
45 cout<<endl;
46}
4748int 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();
6162return0;
63 }
需要指出的是，本例使用的是无向图，但DFS也可以针对有向图。
需要加以说明的是，即使该图中有结点无法保证能到达图中所有结点，但代码中第42行可以保证图中每个结点都会被访问到。
运行结果如下：
文献引用：算法导论->22章->基本图算法
代码参考：http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/
原文：http://www.cnblogs.com/lxiao/p/4320601.html
内容总结
以上是互联网集市为您收集整理的算法系列之图--DFS全部内容，希望文章能够帮你解决算法系列之图--DFS所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。