#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);
}
}
~Graph()
{
delete []adj;
}
void isCycle();
void isCyclicUtil(int v,bool visited[],bool rec[]);
};
void Graph::isCyclicUtil(int v,bool visited[],bool rec[])
{
if(!visited[v])
{
visited[v]=true;
rec[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,rec);
}
else
if(rec[*it])
{
for(int i=0;i<k;i++)
cout<<circle[i]<<" ";
cout<<endl;
}
}
rec[v]=false;
visited[v]=false;
k--;
}
}
void Graph::isCycle()
{
bool *visited=new bool[V];
bool *rec=new bool[V];
for(int i=0;i<V;i++)
{
visited[i]=false;
rec[i]=false;
}
isCyclicUtil(0,visited,rec);
}
int main()
{
Graph g;
cout<<"All possible Cycles :"<<endl;
g.isCycle();
return 0;
}Program to print all elementary cycles in a directed graph
Subscribe to:
Posts (Atom)
No comments:
Post a Comment