Showing posts with label detect cycle in graph. Show all posts
Showing posts with label detect cycle in graph. Show all posts

Saturday, November 7, 2015

Detect Cycle in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}

int  dfs(graph *g,int k,int visited[],int recstack[])
{

if(!visited[k]){
recstack[k]=1;
visited[k]=1;

for(int j=0;j<g->vec[k].size();j++)
{


if(!visited[g->vec[k][j]]&&dfs(g,g->vec[k][j],visited,recstack))
{
return 1;
}
else if(recstack[g->vec[k][j]])
return 1;
}
}
recstack[k]=0;
return 0;
}
 int main()
{
int visited[100],recstack[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 0);
    addEdge(g, 3, 4);
   
    for(int i=0;i<100;i++)
{
recstack[i]=0;
visited[i]=0;
}
for (int i = 0; i < 5; i++)
{
for(int i1=0;i1<100;i1++)
{
recstack[i1]=0;
visited[i1]=0;
}
   if(dfs(g,i,visited,recstack))
   {
    cout<<" Cycle present ";
    break;
   }
 
}

return 0;
}

Thursday, July 23, 2015

detect cycle in graph

#include <iostream>
#include <vector>
#include<fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
bool DFS(int s,vector < vector < int > > v,bool c[200],bool rec[100])
{
if(!c[s])
{
std::vector<int > ::iterator it;
rec[s]=true;
c[s]=true;
for(it=v[s].begin();it!=v[s].end();++it)
{
if(!c[*it]&&DFS(*it,v,c,rec))
return true;
else if(rec[*it])
return true;
}

}
rec[s]=false;
return false;
}
int main()
{
vector < vector <  int >  > v;
bool c[200],rec[100];
for (int i = 0; i < 200; i++)
{
c[i]=false;
rec[i]=false;
}
ifstream fin;
fin.open("/home/pawan/Desktop/input1.txt");
if(!fin.is_open())
{
cout<<" file not open";
return 0;
}

int n;
fin>>n;
v.resize(n);
int i,j,w;

while(!fin.eof())
{
fin>>i>>j>>w;
v[i].push_back(j);
}
for (i = 0; i < v.size(); i++)
{
std::vector<int >::iterator it;
cout<<i<<"-> ";
for(it=v[i].begin();it<v[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
bool result= DFS(1,v,c,rec);
if(result)
cout<<"cycle exist";
else
cout<<"cycle free";
return 0;

}

Contributors

Translate