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

Sample Input:

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

Sample Output:

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.LinkedList;
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
 *
 */
public class BreadthFirstSearchShortestReach {
	
	/**
	 * 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;
		final List<Node> linkedNodes = new LinkedList<>();
		private Node(int id) {
			this.id = id;
		}
		
		/**
		 * Links the input node to this node by adding it to linkedNodes list.
		 */
		private void addLinkedNode(Node node) {
			linkedNodes.add(node);
		}
		
		/**
		 * Gets all the linkedNodes to this node.
		 */
		private List<Node> getLinkedNodes() {
			return linkedNodes;
		}
			
	}
	
	/**
	 * 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
				secondQueue.addAll(tmpNode.getLinkedNodes());
			}
			// 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
				firstQueue.addAll(tmpNode.getLinkedNodes());
			}
			// 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
				xNode.addLinkedNode(yNode);
				yNode.addLinkedNode(xNode);
			}
			
			// 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.