摘要：
算法系列之图--探查环==分割==DFS可以被用来探查图中环的存在。仅有当一个图中存在‘回边’（backedge）时可以判定图中存在环。’回边‘是一条边，该边从一个结点到该结点或者到达该结点在DFS中的祖先。下图有三条‘回边’，也就有三个环代码例子：1#include<iostream>2#include<limits.h>3#include<list>4usingnamespacestd;56classGraph{7intv;//结点数8list<int>*adj;//邻接表9boolisCyclicUtil(intv,boolvisited[],bool*stack);10public:11Graph(intv);12voidaddEdge(intu,intv);13boolisCyclic();14};1516Graph::Graph(intv){17this->v=v;18this->adj=newlist<int>[v];19}2021voidGraph::addEdge(intu,intv){22adj[u].push_back(v);23}2425boolGraph::isCyclicUtil(intv,boolvisited[],boolresStack[]){26if(visited[v]==false){27cout<<v<<"";28visited[v]=true;29resStack[v]=true;30list<int>::iteratoriter=adj[v].begin();31for(;iter!=adj[v].end();iter++){32if(!visited[*iter]&&isCyclicUtil(*iter,visited,resStack))33returntrue;34elseif(resStack[*iter])35returntrue;36}37}38resStack[v]=false;39returnfalse;40}4142boolGraph::isCyclic(){43bool*visited=newbool[v];44bool*resStack=newbool[v];45for(inti=0;i<v;i++){46visited[i]=false;47resStack[i]=false;48}49for(inti=0;i<v;i++)50if(isCyclicUtil(i,visited,resStack))51returntrue;52returnfalse;53}5455intmain()56{57Graphg=Graph(4);58g.addEdge(2,0);59g.addEdge(2,3);60g.addEdge(0,1);61g.addEdge(0,2);62g.addEdge(3,3);63g.addEdge(1,2);6465if(g.isCyclic())66cout<<"Graphhasacycle"<<endl;67else68cout<<"Graphhasnocycle"<<endl;6970return0;71}运行结果为：代码参考：http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
DFS可以被用来探查图中环的存在。仅有当一个图中存在‘回边’（back edge）时可以判定图中存在环。’回边‘是一条边，该边从一个结点到该结点或者到达该结点在DFS中的祖先。
下图有三条‘回边’，也就有三个环
代码例子：
1 #include <iostream> 2 #include <limits.h> 3 #include <list> 4 using namespacestd; 5 6 classGraph{ 7 int v;//结点数 8 list<int> *adj;//邻接表 9 bool isCyclicUtil(int v,bool visited[],bool *stack); 10 public: 11 Graph(intv); 12 void addEdge(int u,intv); 13 boolisCyclic(); 14 }; 15 16 Graph::Graph(intv){ 17 this->v =v; 18 this->adj = new list<int>[v]; 19 } 20 21 void Graph::addEdge(int u,intv){ 22 adj[u].push_back(v); 23 } 24 25 bool Graph::isCyclicUtil(int v,bool visited[],boolresStack[]){ 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 boolGraph::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 intmain() 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/