Recent Tutorials and Articles
HackerRank Solution: BFS Shortest Reach
Published on: 2018-05-25 16:05:10

This tutorial provides Java solution to "Breadth First Search: Shortest Reach" challenge of HackerRank.

# Hackerrank Challenge Details

### 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. This will be done for all nodes same as in the order of input 1 to N.

For unreachable nodes, print -1.

### Constraints:

• 1 < T < 10
• 2 < N < 1000
• 1 < M < (N x (N - 1) / 2)
• 1 < x,y,S < N

2
4 2
1 2
1 3
1
3 1
2 3
2

6 6 -1
-1 6

### Explanation:

For test cases 1:

The graph given in the test case is shown as :

S denotes the node 1 in the test case and B,C and D denote 2,3 and 4. Since S is the starting node and the shortest distances from it are (1 edge, 1 edge, Infinity) to the nodes B,C and D (2,3 and 4) respectively.

Node D is unreachable, hence -1 is printed (not Infinity).

For test cases 2: There are only one edge (2, 3) in a graph with 3 nodes, so node 1 is unreachable from node 2, and node 3 has one edge from node 2, each edge has the length of 6 units. So we output -1 6.

# Solution Details

## Java Implementation:

package com.saintech.allprogtutorials.hackerrank.algos;

import java.util.List;
import java.util.Queue;
import java.util.Scanner;

/**
* @author Sain Technology Solutions
*
* Solution to Problem - https://www.hackerrank.com/challenges/bfsshortreach
*
*/

/**
* Represents Node of the graph and contains node id along with the nodes that are attached to it.
*
*/
private static class Node {
final int id;
private Node(int id) {
this.id = id;
}

/**
*/
}

/**
* Gets all the linkedNodes to this node.
*/
}

}

/**
* Calculates the distance between two input nodes.
*
* @param N containing total number of nodes.
* @param node1 First node of the nodes to calculate distance between.
* @param node2 Second node of the nodes to calculate distance between.
* @return distance between two nodes or -1 if nodes are not connected.
*/
private static int calculateDistance(int N, Node node1, Node node2) {
//If any of node is null, input nodes are not connected and we return -1.
if(node1 == null || node2 == null) {
return -1;
}
// Sets edge length to 6 as mentioned in challenge
final int edgeLength = 6;

// Applies breadth first search (level order traversal) using two queues for
// traversing alternate levels starting from level 0 means node1
int level = 0;

// Uses LinkedList as queues since it implements Queue interface and provides implementation
// for queue methods.
final Queue<Node> firstQueue = new LinkedList<>();
final Queue<Node> secondQueue = new LinkedList<>();

// Adds node1 to first queue to start loop
firstQueue.offer(node1);

// An array to keep note of visited nodes
final boolean[] visitedNodes = new boolean[N];

while(!firstQueue.isEmpty() || !secondQueue.isEmpty()) {
while(!firstQueue.isEmpty()) {
final Node tmpNode = firstQueue.poll();
// Ignore the visited nodes
if(visitedNodes[tmpNode.id]) {
continue;
}

if(tmpNode.id == node2.id) {
return level * edgeLength;
}

// mark the current node as visited
visitedNodes[tmpNode.id] = true;
// add all linked nodes of this node to second queue to traverse after current
// queue nodes (this level) have been visited
}
// Increment the level as we move to next level after we have traversed all the elements of a queue
level++;

while(!secondQueue.isEmpty()) {
final Node tmpNode = secondQueue.poll();
// Ignore the visited nodes
if(visitedNodes[tmpNode.id]) {
continue;
}

if(tmpNode.id == node2.id) {
return level * edgeLength;
}
// mark the current node as visited
visitedNodes[tmpNode.id] = true;
// add all linked nodes of this node to first queue to traverse after current
// queue nodes (this level) have been visited
}
// Increment the level as we move to next level after we have traversed all the elements of a queue
level++;
}

return -1;
}

/**
*  We will be using adjacency list model wherein each node will be containing the list of other
*  nodes, it is linked to.
*/
public static void main(String[] args) {
final Scanner in = new Scanner(System.in);
// Get no of test cases
final int T = in.nextInt();
for(int i = 0; i < T; i++) {
// For each test case
// Get no of nodes in graph
final int N = in.nextInt();
// Get no of edges
final int M = in.nextInt();
// Array for storing all the elements of graph. Elements that are not connected are not stored in this array
final Node[] graphElems = new Node[N];
for(int j = 0; j < M; j++) {
// Subtract 1 out of first node id to fit this into our graph elements as array index starts with 0
final int x = in.nextInt() - 1;
// If node is present in array, fetch it, otherwise create a new instance of Node and put in array
Node xNode = graphElems[x];
if(xNode == null) {
xNode = new Node(x);
graphElems[x] = xNode;
}

// Subtract 1 out of second node id to fit this into our graph elements as array index starts with 0
final int y = in.nextInt() - 1;
// If node is present in array, fetch it, otherwise create a new instance of Node and put in array
Node yNode = graphElems[y];
if(yNode == null) {
yNode = new Node(y);
graphElems[y] = yNode;
}
// Since graph is undirected, we set both nodes into each other's linked nodes to have a bi-directional mapping
}

// Subtract 1 out of start node id to fit this into our graph elements as array index starts with 0
final int S = in.nextInt() - 1;
for(int k = 0; k < graphElems.length; k++) {
if(k != S) {
int distance = calculateDistance(N, graphElems[k], graphElems[S]);
System.out.print(distance + " ");
}
}
System.out.println();
}
in.close();
}
}

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

Published on: 2018-05-25 16:05:10