Showing posts with label depth first search in graph. Show all posts
Showing posts with label depth first search in graph. Show all posts

Friday, November 6, 2015

DFS and BFS of undirected 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);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k,int visited[])
{
queue <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
void dfs(graph *g,int k,int visited[])
{
stack <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.top();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
 int main()
{
int visited[100];
for(int i=0;i<100;i++)
visited[i]=0;
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, 3);
    addEdge(g, 3, 4);
    dfs(g,0,visited);
    cout<<endl;
    for(int i=0;i<100;i++)
visited[i]=0;
    bfs(g,2,visited);
return 0;
}

Thursday, July 23, 2015

depth first search in graph

#include <iostream>
#include <vector>
#include <fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
void DFS(int s,vector < vector < int > > v,bool c[200])
{

std::vector<int > ::iterator it;
cout<<s<<"->";
c[s]=true;
for(it=v[s].begin();it!=v[s].end();++it)
{
if(!c[*it])
{
c[*it]=true;

DFS(*it,v,c);
}
}

}
int main()
{
vector < vector <  int >  > v;
bool c[200];
for (int i = 0; i < 200; i++)
{
c[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);
v[j].push_back(i);
n--;
}
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;
}
DFS(1,v,c);

}





input1.txt

15 0 2 6 1 2 5 2 3 1 1 4 6 2 7 7 4 7 4 3 6 8 4 5 12 5 8 4 8 7 2 8 11 7 11 6 4 5 9 11 9 10 8 10 11 2

Contributors

Translate