Shortest Path Using BFS in a Graph
#include<bits/stdc++.h>
using namespace std;
class Graph{
int v;
list<int> *l;
public:
Graph(int V){
v=V;
l= new list<int>[v];
}
void addEdge(int i,int j,bool undir=true){
l[i].push_back(j);
if(undir)
l[j].push_back(i);
}
void print(){
for (int i = 0; i < v; i++)
{
cout<<i<<"--> ";
for(auto num:l[i]){
cout<<num<<" ";
}
cout<<endl;
}
}
void bfs(int source,int dest=-1){
queue<int>q;
bool * visited= new bool[v]{0};
int * parent= new int[v];
int * dist= new int[v];
q.push(source);
visited[source]=true;
while(!q.empty()){
int f=q.front();
q.pop();
cout<<f<<" ->";
for(auto nbr:l[f]){
if(!visited[nbr]){
// cout<<nbr<<" ";
q.push(nbr);
parent[nbr]=f;
dist[nbr]=dist[f]+1;
}
visited[nbr]=true;
}
cout<<endl;
}
for (int i = 0; i < v; i++)
{
cout<<"Shortest distance to "<<i<<" is"<<dist[i]<<endl;
}
if(dest!=-1){
int temp=dest;
while(temp!=source){
cout<<temp<<"--";
temp=parent[temp];
}
cout<<temp;
}
}
};
int main(){
Graph g(7);
g.addEdge(0,1);
g.addEdge(1,2);
g.addEdge(3,5);
g.addEdge(5,6);
g.addEdge(4,5);
g.addEdge(0,4);
g.addEdge(3,4);
g.addEdge(2,3);
g.print();
g.bfs(1,6);
return 0;
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.