当前位置:   article > 正文

算法系列之图--探查环

图计算探查表

  DFS可以被用来探查图中环的存在。仅有当一个图中存在‘回边’(back edge)时可以判定图中存在环。’回边‘是一条边,该边从一个结点到该结点或者到达该结点在DFS中的祖先。

  下图有三条‘回边’,也就有三个环

  

代码例子:

 1 #include <iostream>
 2 #include <limits.h>
 3 #include <list>
 4 using namespace std;
 5 
 6 class Graph{
 7     int v;//结点数
 8     list<int> *adj;//邻接表
 9     bool isCyclicUtil(int v,bool visited[],bool *stack);
10 public:
11     Graph(int v);
12     void addEdge(int u,int v);
13     bool isCyclic();
14 };
15 
16 Graph::Graph(int v){
17     this->v = v;
18     this->adj = new list<int>[v];
19 }
20 
21 void Graph::addEdge(int u,int v){
22     adj[u].push_back(v);
23 }
24 
25 bool Graph::isCyclicUtil(int v,bool visited[],bool resStack[]){
26     if (visited[v] == false){
27         cout<<v<<" ";
28         visited[v] = true;
29         resStack[v] = true;
30         list<int>::iterator iter = adj[v].begin();
31         for (;iter != adj[v].end();iter++){
32             if (!visited[*iter] && isCyclicUtil(*iter,visited,resStack))
33                 return true;
34             else if (resStack[*iter])
35                 return true;
36         }
37     }
38     resStack[v] = false;
39     return false;
40 }
41 
42 bool Graph::isCyclic(){
43     bool *visited = new bool[v];
44     bool *resStack = new bool[v];
45     for (int i=0;i<v;i++){
46         visited[i] = false;
47         resStack[i] = false;
48     }
49     for (int i=0;i<v;i++)
50         if (isCyclicUtil(i,visited,resStack))
51             return true;
52     return false;
53 }
54 
55 int main()
56 {
57     Graph g = Graph(4);
58     g.addEdge(2,0);
59     g.addEdge(2,3);
60     g.addEdge(0,1);
61     g.addEdge(0,2);
62     g.addEdge(3,3);
63     g.addEdge(1,2);
64 
65     if (g.isCyclic())
66         cout<<"Graph has a cycle"<<endl;
67     else
68         cout<<"Graph has no cycle"<<endl;
69 
70     return 0;
71 }

 

运行结果为:

 

 

代码参考:http://www.geeksforgeeks.org/detect-cycle-in-a-graph/

转载于:https://www.cnblogs.com/lxiao/p/4346448.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/64529
推荐阅读
相关标签
  

闽ICP备14008679号