Shortest Path Using BFS in a Graph

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

Post a Comment

0 Comments