#include<iostream> #include<list> using namespace std; int circle[100]; int k=0; class Graph { int V,E; list<int> *adj; public: Graph() { cout<<endl<<"Enter the no of vertices and edges:"; cin>>V>>E; adj=new list<int>[V]; int v1,v2; for(int i=0;i<E;i++) { cout<<endl<<"Enter the vertices for edge "<<i+1<<" :"; cin>>v1>>v2; adj[v1].push_back(v2); adj[v2].push_back(v1); } } ~Graph() { delete []adj; } void isCycle(); void isCyclicUtil(int v,bool visited[],int parent); }; void Graph::isCycle() { bool* visited=new bool[V]; for(int i=0;i<V;i++) visited[i]=false; // for(int u=0;u<V;u++) // if(!visited[u]) isCyclicUtil(0,visited,-1); } void Graph::isCyclicUtil(int v,bool visited[],int parent) { visited[v]=true; circle[k++]=v; list<int>::iterator it; for(it=adj[v].begin();it!=adj[v].end();++it) { if(!visited[*it]) { isCyclicUtil(*it,visited,v); } else if(*it!=parent) { for(int i=0;i<k;i++) cout<<circle[i]<<" "; cout<<endl; } } visited[v]=false; k--; } int main() { Graph g; cout<<endl<<"All possible cycles :"<<endl; g.isCycle(); //cout<<endl<<"Contain cycle"; //else //cout<<endl<<"Doesn't Contain Cycle"; }
Program to print all elementary cycles in an Undirected Graph
Subscribe to:
Posts (Atom)
No comments:
Post a Comment