Example of BFS, level EASY

BFS_example.cpp

/*
 *  DEMO OF BFS (Breadth First Search)
 ***************************************
 * 
 * PROBLEM STATEMENT
 *-------------------
 * Given an undirected graph consisting of N nodes (labelled 1 to N) where 
 * a specific given node S represents the start position and an edge between 
 * any two nodes is of length 6 units in the graph.
 *
 * It is required to calculate the shortest distance from start position (Node S) 
 * to all of the other nodes in the graph.
 *
 * Note 1: If a node is unreachable , the distance is assumed as −1. 
 * Note 2: The length of each edge in the graph is 6 units.
 *
 *
 * INPUT FORMAT
 *--------------
 * The first line contains T, denoting the number of test cases. 
 * First line of each test case has two integers N, denoting the number 
 * of nodes in the graph and M, denoting the number of edges in the graph. 
 * The next M lines each consist of two space separated integers x y, 
 * where x and y denote the two nodes between which the edge exists. 
 * The last line of a testcase has an integer S, denoting the starting position.
 *
 *
 * OUTPUT FORMAT
 *---------------
 * For each of T test cases, print a single line consisting of N−1 space separated integers, 
 * denoting the shortest distances of the N-1 nodes from starting position S.
 * For unreachable nodes, print −1.
 */


#include <iostream>
#include <map>              // We use map and vector to implement the graph 
#include <vector>           // with minimum efforts, like an adjecency list, but faster.
#include <queue>            // We need the queue for the BFS

using namespace std;
typedef map<int, vector<int> > graph;   // This is how we will represent the graph, node --> list of children nodes

void doBFS(graph &g, vector<int> &dist, int src){
    queue<int> q;
    int v;
    q.push(src);            // enqueue the source vertex

    while(! q.empty()){     // while the queue is not empty
        v = q.front();      // dequeue the vertex at the front and say it vertex v
        q.pop();

        for(int i=0; i<g[v].size(); ++i) {      //
            if(dist[g[v][i]] == -1){            // For all unvisited children of v
                dist[g[v][i]] = dist[v]+6;      // update the distance from source
                q.push(g[v][i]);                // and enqueue them
            }
        }
    }                                           // That's it, so simple and our BFS is done :)
}


int main(){
    int T, M, N, u, v, s;
    cin >> T;                   // Read the number of testcases
    while(T--){                 // For each test case
        cin >> N >> M;          // read the values of N and M
        vector<int> distance(N+1, -1);                  // init the distance vector, assume the distance of each 
                                                        // node from source is INFINITE, denoted -1
        graph g;                                        
        for(int i=1; i<=N; ++i) g[i] = vector<int>();   // init the graph
        while(M--){
            cin >> u >> v;                              // for each edge, read the corresponding vertices
            g[u].push_back(v);                          // and accordingly add them to the graph
            g[v].push_back(u);
        }
        cin >> s;                                       // read the source vertex
        distance[s] = 0;                                // distance of source from itself is 0, obviously

        doBFS(g, distance, s);      ///////////////////  DO THE BFS ///////////////////

        for(int i=1; i<=N; i++) if(i != s) cout <<  distance[i] << " "; // and print the distance vector :D
        cout << endl;
    }
    return 0;           // voila, we are done :)
}