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;
}

No comments:

Post a Comment

Contributors

Translate