# HackerRank BFS: Shortest Reach in a Graph solution

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.

## 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;
public GraphNode(int numNodes){
this.sumNodes = numNodes;
for(int i = 0; i < numNodes; i++){
}
}
public void addEdge(int a, int b){
}
}

public class Solution {

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;
if(!isVisited[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();
}
int s = sc.nextInt();
int[] results = new int[n];
Arrays.fill(results, -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:
int V;
Graph(int n) {
adj = vector<vector<int> >(n , vector<int>());
V = n;
}

void add_edge(int u, int v) {
}

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 ){
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;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
// add each edge to the graph
}
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
{
}list;
void Insert(list *A,int src,int des)
{
node * temp = malloc(sizeof(node));
temp -> data  = des;
}
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++];
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++)
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);

//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];

}

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;
return input[currentLine++];
}
function processData(input) {
var data = input.split('\n');

for (var i = 0; i < queries; i++) {

//console.log('data',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++) {
edges.push([parseInt(edge[0]), parseInt(edge[1])]);
}

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