网站建设话术宝典,怎么自己做网站qq,安卓手机做网站服务器吗,三亚北京网站建设深度优先搜索使用的策略是#xff0c;只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索#xff0c;知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了#xff0c;搜索就回溯到v的前驱结点#xff08;v是经该结点才被发现的… 深度优先搜索使用的策略是只要与可能就在图中尽量“深入”。DFS总是对最近才发现的结点v出发边进行探索知道该结点的所有出发边都被发现为止。一旦v的所有出发边都被发现了搜索就回溯到v的前驱结点v是经该结点才被发现的来搜索该前驱结点的出发边。该过程持续知道从源结点可以到达的所有结点都被发现为止。此后若还存在未被发现的结点则DFS将从从未被发现的结点中任选一个结点作为新的源节点并重复同样的过程。 还是老办法上代码可以清楚地解释 1 #include iostream2 #include list3 using namespace std;4 5 class Graph{6 private:7 int v;//结点数8 listint* 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 listint[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 coutu ;
30 listint::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 i0;iv;i)
40 visited[i] false;
41 //递归调用dfsutil函数深度遍历每个结点
42 for (int i0;iv;i)
43 if (visited[i] false)
44 DFSUtil(i,visited);
45 coutendl;
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/转载于:https://www.cnblogs.com/lxiao/p/4320601.html
