In this HackerRank BFS: Shortest Reach in a Graph Interview preparation kit problem there is given a graph, determine the distances from the start node to each of its descendants and return the list in node number order, ascending. If a node is disconnected, its distance should be -1.


HackerRank BFS: Shortest Reach in a Graph solution


Problem solution in Python programming.

t = int(input().strip())

def calculate_cost(nodes, travel_edges):    
    new_edges = []
    weight = 6
    current_cost = 0

    while travel_edges:
        for e in travel_edges:
            id, cost, edges = nodes[e-1]
            
            if cost == -1:
                new_edges = new_edges + edges
                cost = current_cost
                nodes[e-1] = (id, cost, edges)
            
        travel_edges = new_edges
        new_edges = []
        current_cost += weight
                
    return nodes
    
for test in range(t):
    n, m = [int(i) for i in input().strip().split()]
    
    nodes = [(i, -1, []) for i in range(1, n+1)]

    for edge in range(m):
        start, end = [int(i) for i in input().strip().split()]
        
        id, cost, edges = nodes[start-1]
        nodes[start-1] = (id, cost, edges + [end])

        id, cost, edges = nodes[end-1]
        nodes[end-1] = (id, cost, edges + [start])
        
    s = int(input().strip())
    
    nodes = calculate_cost(nodes, [s])
    
    weights = ' '.join([str(node[1]) for node in nodes if node[1] != 0])
    
    print(weights)


Problem solution in Java Programming.

import java.util.*;

class GraphNode{
    int sumNodes;
    ArrayList<LinkedList<Integer>> adjList;
    public GraphNode(int numNodes){
        this.sumNodes = numNodes;
        adjList = new ArrayList<LinkedList<Integer>>();
        for(int i = 0; i < numNodes; i++){
            adjList.add(new LinkedList<Integer>());
        }
    }
    public void addEdge(int a, int b){
        adjList.get(a).add(b);
        adjList.get(b).add(a);
    }
}

public class Solution {

    public static void getDistance(ArrayList<LinkedList<Integer>> adjList, int[] results, int s){
        LinkedList<Integer> q = new LinkedList();
        boolean[] isVisited = new boolean[adjList.size()];
        q.add(s);
        isVisited[s] = true;
        int count = 0;
        while(!q.isEmpty()){
            int qSize = q.size();
            for(int i = 0; i < qSize; i++){
                int removed = q.poll();
                results[removed] = count;
                for(int x: adjList.get(removed)){
                    if(!isVisited[x]){
                        q.add(x);
                        isVisited[x] = true;
                    }
                }
            }
            count += 6;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        for(int i = 1; i <= q; i++){
            int n = sc.nextInt();
            int m = sc.nextInt();
            GraphNode g = new GraphNode(n);
            for(int j = 1; j <= m; j++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                g.addEdge(a-1, b-1);
            }
            int s = sc.nextInt();
            int[] results = new int[n];
            Arrays.fill(results, -1);
            getDistance(g.adjList, results, s-1);
            for(int k = 0; k < n; k++){
                if(k != s-1) System.out.print(results[k]+ " ");
            }
            
            System.out.println();
        }
    }
}


Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 1<<30
class Graph {
    public:
        vector<vector<int> > adj;
        int V;
        Graph(int n) {
            adj = vector<vector<int> >(n , vector<int>());
            V = n;
        }
    
        void add_edge(int u, int v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    
        vector<int> shortest_reach(int start) {
            vector<int> dist( V , INF );
            vector<bool> seen( V , false);
            queue<int> Q;
            dist[start] = 0;
            Q.push(start);
            seen[ start ] = true;
            while( !Q.empty() ){
                int current = Q.front(); Q.pop();
                for( int i = 0 ; i < adj[current].size() ; ++i ){
                    int neighbour = adj[current][i];
                    if( !seen[neighbour] && dist[ neighbour ] > dist[ current ] + 1 ){
                        dist[ neighbour ] = dist[ current ] + 1;
                        Q.push( neighbour );
                        seen[ neighbour ] = true;
                    }
                }
            }
            
            for( int i = 0 ; i <  V ; ++i ){
                if( i != start ){
                    if( dist[i] == INF ) dist[i] = -1;
                    else dist[i] *= 6;
                }
            }
            return dist;
        }
    
};

int main() {
    int queries;
    cin >> queries;
        
    for (int t = 0; t < queries; t++) {
      
      int n, m;
        cin >> n;
        // Create a graph of size n where each edge weight is 6: 
        Graph graph(n);
        cin >> m;
        // read and set edges
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            // add each edge to the graph
            graph.add_edge(u, v);
        }
      int startId;
        cin >> startId;
        startId--;
        // Find shortest reach from node s
        vector<int> distances = graph.shortest_reach(startId);

        for (int i = 0; i < distances.size(); i++) {
            if (i != startId) {
                cout << distances[i] << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
typedef struct node
    {
    int data;
    struct node * next;
}node;
typedef struct list
    {
    node * head;
}list;
void Insert(list *A,int src,int des)
{
    node * temp = malloc(sizeof(node));
    temp -> data  = des;
    temp -> next  = A[src].head;
    A[src].head = temp;
}
void BFS(list *A,int src,int n)
{
    node * temp;
    int i,u,level[n],queue[n];
    int front = 0, rear = 0;
    for(i=0;i<n;i++)
    level[i] = -1;
    queue[front++] = src;
    level[src] = 0;
    while(front>rear)
    {
        u = queue[rear++];
        temp = A[u].head;
        while(temp != NULL)
        {
            if(level[temp->data]==-1)
            {
                queue[front++] = temp->data;
                level[temp->data] = level[u] + 6;
            }
            temp = temp->next;
        }
    }
    
    for(i=0;i<n;i++)
    {
        if(i!=src)
        printf("%d ",level[i]);
    }
    printf("\n");
    
}
int main() {

    int i,j,q,n,m,u,v,s;
    list A[1000];
    scanf("%d",&q);
    for(i=0;i<q;i++)
    {
        scanf("%d%d",&n,&m);
        for(j=0;j<n;j++)
            A[j].head = NULL;
        for(j=0;j<m;j++)
        {
            scanf("%d%d",&u,&v);
            Insert(A,u-1,v-1);
            Insert(A,v-1,u-1);
        }
        
        scanf("%d",&s);
        BFS(A,s-1,n);
    }
    return 0;
}


Problem solution in JavaScript programming.

var shortest = function(v, edges, start) {
    //console.log('v', v, 'edges', edges, 'start', start);
    
    var adj = {};
    
    //Initialize distance array to -1
    var dist = [];
    for (var i = 1; i <= v; i++) {
        dist[i] = -1;
    }
    dist[start] = 0;
    
    for (var i = 0; i < edges.length; i++) {
        var e1 = edges[i][0];
        var e2 = edges[i][1];
        
        adj[e1] = adj[e1] || [];
        adj[e1].push(e2);
        
        adj[e2] = adj[e2] || [];
        adj[e2].push(e1);
    }
    
    var queue = [start];
    
    while (queue.length > 0) {
        var n = queue.shift();
        var currentDist = dist[n];
        var neighbors = adj[n] || [];
        neighbors.forEach(function(neighbor) {
           if (dist[neighbor] === -1) {
               dist[neighbor] = currentDist + 6;
               queue.push(neighbor);
           } 
        });
    }
    
    //filtering is fun, it skips over index 0 on its own because no value
    var res = dist.filter(function(f, index) {
        return index !== start;
    });

    console.log(res.join(' '));
}

var currentLine = 0;
function readLine(input) {
    return input[currentLine++];
}
function processData(input) {
    //Enter your code here
    var data = input.split('\n');
    var queries = parseInt(readLine(data));
    
    for (var i = 0; i < queries; i++) {
        
        //console.log('data',data);
        var a = readLine(data);
        //console.log('a', a);
        var a0 = a.split(' ');
        var vertCount = parseInt(a0[0]);
        var edgeCount = parseInt(a0[1]);
        var edges = [];
        for (var j = 0; j < edgeCount; j++) {
            var edge = readLine(data).split(' ');
            edges.push([parseInt(edge[0]), parseInt(edge[1])]);
        }
        var start = parseInt(readLine(data));

        shortest(vertCount, edges, start);
    }
    
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});