BFS: Shortest Reach in a Graph

  • + 0 comments

    Below is the simple C++ solution

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    void BFS(vector<int> adj[], int visited[], int s)
    {
        queue<int> Q;
        Q.push(s);
        visited[s] = 0;
        
        while(!Q.empty())
        {
            int node = Q.front();
            Q.pop();
            
            for(int i = 0; i < adj[node].size(); ++i)
            {
                if(visited[adj[node][i]] == -1)
                {
                    visited[adj[node][i]] = 0;
                    visited[adj[node][i]] = 6 + visited[node];
                    Q.push(adj[node][i]); // Pushing all the neighbouring nodes to the queue
                }
            }
        }
    }
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        int q;
        cin >> q;
        for(int i = 0; i < q; ++i)
        {
            int n, m, u, v, s;
            cin >> n >> m;
            vector<int> adj[n+1];
            for(int j = 1; j <= m; ++j)
            {
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
            cin >> s;
            int visited[n+1];
            for(int i = 1; i <= n; ++i)
                visited[i] = -1;
            
            BFS(adj, visited, s);
            
            for(int i = 1; i <= n ; ++i)
            {
                if(visited[i] != 0)
                cout << visited[i] << " ";
            }
            cout << endl;
        }
        
        return 0;
    }