Showing posts with label Distance between two vertices in Graph. Show all posts
Showing posts with label Distance between two vertices in Graph. Show all posts

Saturday, November 7, 2015

Distance between two vertices in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
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 k1,int visited[],int dist[])
{
queue <int > s;
s.push(k1);
visited[k1]=1;

for(int i=0;i<100;i++)
dist[i]=-1;
dist[k1]=0;
int k;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";

for(int j=0;j<g->vec[k].size();j++)
{
if(dist[g->vec[k][j]]==-1)
{
s.push(g->vec[k][j]);
visited[g->vec[k][j]]=1;
dist[g->vec[k][j]]=dist[k]+1;
}
}
}
}

 int main()

{
int visited[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, 3);
    addEdge(g, 3, 4);
   
    cout<<endl;
    int dist[100];
    for(int i=0;i<100;i++)
visited[i]=0,dist[i]=-1;
    bfs(g,2,visited,dist);
    cout<<" Shortest distance between 2 and 0 is "<<dist[0];
return 0;
}

Contributors

Translate