In this post, we will solve HackerRank Breadth First Search: Shortest Reach Problem Solution.
Consider an undirected graph where each edge weighs 6 units. Each of the nodes is labeled consecutively from 1 to n.
You will be given a number of queries. For each query, you will be given a list of edges describing an undirected graph. After you create a representation of the graph, you must determine and report the shortest distance to each of the other nodes from a given starting position using the breadth-first search algorithm (BFS). Return an array of distances from the start node in node number order. If a node is unreachable, return for that node.
Example
The following graph is based on the listed inputs:
n = 5 // number of nodes
m = 3 // number of edges
edges = [1, 2], [1, 3], [3, 4]
8 = 1 // starting node
All distances are from the start node 1. Outputs are calculated for distances to nodes 2 through 5: [6, 6, 12, -1]. Each edge is 6 units, and the unreachable node 5 has the required return distance of -1.
Function Description
Complete the bfs function in the editor below. If a node is unreachable, its distance is -1.
bfs has the following parameter(s):
- int n: the number of nodes
- int m: the number of edges
- int edges[m][2]: start and end nodes for edges
- int s: the node to start traversals from
Returns
int[n-1]: the distances to nodes in increasing node number order, not including the start node (-1 if a node is not reachable)
Input Format
The first line contains an integer q, the number of queries. Each of the following a sets of lines has the following format:
- The first line contains two space-separated integers n and m, the number of nodes and edges in the graph.
- Each line i of the m subsequent lines contains two space-separated integers, u and v, that describe an edge between nodes u and v.
- The last line contains a single integer, s, the node number to start from.
Sample Input
2
4 2
1 2
1 3
1
3 1
2 3
2
Sample Output
6 6 -1
-1 6
Explanation
We perform the following two queries:
- The given graph can be represented as:
where our start node, s, is node 1. The shortest distances from 8 to the other nodes are one edge to node 2, one edge to node 3, and an infinite distance to node 4 (which it is not connected to). We then return an array of distances from node 1 to nodes 2, 3, and
4 (respectively): [6, 6, -1].
- The given graph can be represented as:
where our start node, s, is node 2. There is only one edge here, so node 1 is unreachable from node 2 and node 3 has one edge connecting it to node 2. We then return an array of distances from node 2 to nodes 1, and 3 (respectively): [−1, 6].
Note: Recall that the actual length of each edge is 6, and we return -1 as the distance to any node that is unreachable from s.
Breadth First Search: Shortest Reach C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int i,j,t,n,m,x,y,s,st,a[1200][1200],b[3000],c[3000],k,le,ee,lee,ff,kkk;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d%d",&n,&m);
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
a[j][k]=360;
}
b[j]=360;
c[j]=0;
}
for(j=1;j<=m;j++)
{
scanf("%d%d",&x,&y);
s=6;
if(a[x][y]>s)
{
a[x][y]=s;
a[y][x]=s;
}
}
scanf("%d",&st);ee=st;
b[st]=0;
c[st]=-1;
for(k=1;k<n;k++)
{
le=10000;lee=st;ff=0;
for(j=1;j<=n;j++)
{
if(c[j]!=-1){
if(b[j]>(b[st]+a[st][j]))
{
b[j]=b[st]+a[st][j];
}
if((b[j]<le)&&(b[j]!=360))
{
le=b[j];
lee=j;
ff=1;
}
}
}
if(ff==1){
st=lee;
c[st]=-1;}
}
kkk=-1;
for(k=1;k<=n;k++){
if(k!=ee){
if((c[k]==0)||(b[k]==360))
printf("%d\t",kkk);
else
printf("%d\t",b[k]);}}
printf("\n");
}
return 0;
}
Breadth First Search: Shortest Reach C++ Solution
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <functional>
#include <queue>
#include <algorithm>
#include <list>
#include <climits>
using namespace std;
struct graph {
std::vector< std::vector<int> > edges;
};
std::function<bool(int, int)> generate_compare_func(std::vector<int> &ref) {
return [&ref](int i1, int i2) {
return ref.at(i1 - 1) > ref.at(i2 - 1);
};
}
// weirdest Dijkstra's implementation I've ever written
std::vector<int> solve(graph& g, int N, int M, int S) {
std::vector<int> dist(N, 7201);
dist.at(S - 1) = 0;
std::set<int> worklist;
for (int i = 0; i < N; i++) {
worklist.insert(i + 1);
}
std::function<bool(int,int)> ref_func = generate_compare_func(dist);
while (worklist.size() > 0) {
std::priority_queue<int, std::vector<int>, decltype(ref_func)> graphPQ(ref_func);
for (std::set<int>::iterator it = worklist.begin(); it != worklist.end(); ++it) {
graphPQ.push(*it);
}
int nextNode = graphPQ.top();
graphPQ.pop(); //gets the minimum distance from start.
// to be honest I could have done this in many other ways other than std::priority_queue
// but this looked cool
worklist.erase(nextNode);
for (int i = 0; i < N; i++) {
//cout << "nextNode: " << nextNode << ", i: " << i << " ";;
if (g.edges[nextNode-1][i]) {
//cout << "true" << endl;
int alt = dist.at(nextNode - 1) + 6;
if (alt < dist.at(i)) {
dist.at(i) = alt;
}
}
}
}
for (std::vector<int>::iterator it = dist.begin(); it != dist.end(); ++it) {
if (*it == 7201) {
*it = -1;
}
}
dist.erase(dist.begin()+S-1);
return dist;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
std::vector< std::vector<int> > currentEdges;
graph g {
.edges = currentEdges
};
int N;
int M;
cin >> N >> M;
for (int j = 0; j < N; j++) {
std::vector<int> edges_from_j(N, 0);
g.edges.push_back(edges_from_j);
}
for (int j = 0; j < M; j++) {
int v1;
int v2;
cin >> v1 >> v2;
g.edges[v1-1][v2-1] = 1;
g.edges[v2-1][v1-1] = 1;
}
int S;
cin >> S;
vector<int> soln = solve(g, N, M, S);
for (int j = 0; j < soln.size(); j++) {
cout << soln.at(j);
if (j != soln.size() - 1) {
cout << " ";
}
}
cout << std::endl;
}
return 0;
}
Breadth First Search: Shortest Reach C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(string[] args)
{
int testCases;
string sTestCase = Console.ReadLine();
if (int.TryParse(sTestCase, out testCases) && testCases <= 10 && testCases >= 1)
{
for (int testCaseIterator = 0; testCaseIterator < testCases; testCaseIterator++)
{
int totalEdges, totalVertices;
string[] input = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
Graph grph = new Graph();
if (input.Length == 2 && int.TryParse(input[0], out totalVertices) && int.TryParse(input[1], out totalEdges))
{
if (totalVertices > 1000 || totalVertices < 2 || totalEdges < 1 || totalEdges > (totalVertices * (totalVertices - 1) / 2))
return;
List<Vertex> queue = new List<Vertex>();
for (int index = 1; index <= totalVertices; index++)
{
Vertex vertex = new Vertex(index);
grph.addVertex(vertex);
}
for (int index = 0; index < totalEdges; index++)
{
string[] edgePair = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if (edgePair.Length == 2)
{
int vrtxA = Convert.ToInt32(edgePair[0]);
int vrtxB = Convert.ToInt32(edgePair[1]);
if (vrtxA > totalVertices || vrtxA < 1 || vrtxB > totalVertices || vrtxB < 1)
return;
Vertex v1 = grph.getVertex(vrtxA);
Vertex v2 = grph.getVertex(vrtxB);
grph.addNeighbours(v1, v2);
}
}
int startingPos = Convert.ToInt32(Console.ReadLine());
if (startingPos > totalVertices || startingPos < 1)
return;
Vertex startingVertex = grph.getVertex(startingPos);
startingVertex.level = 0;
startingVertex.distance = 0;
queue.Add(startingVertex);
BFS(grph, queue);
for (int index = 1; index <= totalVertices; index++)
{
if (index != startingPos)
Console.Write(grph.getVertex(index).distance + " ");
}
//Console.WriteLine("{0}", TotalAstronautsPairPossible);
}
Console.WriteLine();
}
}
}
static void BFS(Graph g, List<Vertex> queue)
{
int index = 0;
while (queue.Count > index)
{
List<Vertex> neighbours = queue[index].getNeighbours();
queue[index].setVertexExplored();
foreach (Vertex vrtx in neighbours)
{
if (!vrtx.isVertexExplored())
{
queue.Add(vrtx);
if (vrtx.level == -1)
{
vrtx.level = queue[index].level + 1;
vrtx.distance = vrtx.level * 6;
}
}
}
index++;
}
}
}
class Vertex
{
public int data;
private List<Vertex> neighbours;
private bool isTraversed;
public int distance;
public int level;
public Vertex(int data)
{
this.data = data;
isTraversed = false;
neighbours = new List<Vertex>();
this.distance = -1;
this.level = -1;
}
public void addNeighbour(Vertex vertexB)
{
if (!neighbours.Any(f => f.data == vertexB.data))
{
this.neighbours.Add(vertexB);
}
}
public void removeNeighbour(Vertex vertexB)
{
int totalNeighbours = neighbours.Count;
for (int index = 0; index < totalNeighbours; index++)
{
if (neighbours[index].data == vertexB.data)
{
neighbours.RemoveAt(index);
break;
}
}
}
public List<Vertex> getNeighbours()
{
return neighbours;
}
public string printNeighbours()
{
string neighboursList = string.Empty;
foreach (Vertex tmpVertex in this.neighbours)
{
neighboursList += tmpVertex.data.ToString() + ",";
}
return neighboursList;
}
public bool isVertexExplored()
{
return isTraversed;
}
public void setVertexExplored()
{
isTraversed = true;
}
}
class Graph
{
private List<Vertex> vertexList;
public Graph()
{
if (vertexList == null)
{
vertexList = new List<Vertex>();
}
}
public void addVertex(Vertex vertex)
{
this.vertexList.Add(vertex);
}
public bool isVertexExists(Vertex vertex)
{
foreach (Vertex tmpVertex in vertexList)
{
if (tmpVertex.data == vertex.data)
return true;
}
return false;
}
public Vertex getVertex(int key)
{
foreach (Vertex tmpVertex in vertexList)
{
if (tmpVertex.data == key)
return tmpVertex;
}
Vertex vertex = new Vertex(key);
this.addVertex(vertex);
return vertex;
}
public void addNeighbours(Vertex from, Vertex to)
{
from.addNeighbour(to);
to.addNeighbour(from);
}
public List<Vertex> getAllVertices()
{
return vertexList;
}
//public List<Vertex>
}Breadth First Search: Shortest Reach Java Solution
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
* @author Kanahaiya Gupta
*
*/
class Graph {
private final int V;
private int E;
private ArrayList<Integer>[] adj;
@SuppressWarnings("unchecked")
Graph(int V) {
adj = (ArrayList<Integer>[]) new ArrayList[V + 1];
this.V = V;
this.E = 0;
for (int v = 1; v <= V; v++)
adj[v] = new ArrayList<Integer>(V);
}
Graph(Scanner in) {
this(in.nextInt());
int E = in.nextInt();
for (int i = 0; i < E; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
class BreadthFirstPaths {
private int s;
private boolean marked[];
private int edgeTo[];
BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V() + 1];
this.s = s;
edgeTo = new int[G.V() + 1];
bfs(G, s);
}
private void bfs(Graph G, int s) {
Queue<Integer> q = (Queue<Integer>) new LinkedList<Integer>();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = v;
q.add(w);
}
}
}
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x])
path.push(x);
path.push(s);
return path;
}
public boolean hasPathTo(int v) {
return marked[v];
}
}
public class BreadthFirstSearchShortestReach {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
Graph G = new Graph(sc);
int s = sc.nextInt();
BreadthFirstPaths bfp = new BreadthFirstPaths(G, s);
for (int v = 1; v <= G.V(); v++) {
if (s != v) {
if (bfp.hasPathTo(v)) {
Stack<Integer> st = (Stack<Integer>) bfp.pathTo(v);
int sum = 0;
for (int x = 1; x < st.size(); x++) {
sum += 6;
}
System.out.print(sum + " ");
} else {
System.out.print(-1 + " ");
}
}
}
System.out.println();
}
}
}Breadth First Search: Shortest Reach JavaScript Solution
function solve(graph, queue) {
var weights = {};
while (queue.length) {
var n = queue.shift();
var nextNodes = graph[n.node];
var nextNodesLen = nextNodes.length;
if (weights.hasOwnProperty(n.node)) continue;
weights[n.node] = n.weight;
for (var i = 0; i < nextNodesLen; i++) {
if (!weights.hasOwnProperty(nextNodes[i])) {
queue.push({node: nextNodes[i], weight: n.weight + 6});
}
}
}
return weights;
}
function formatSolution(weights, nodeCount) {
var solution = [];
for (var i = 1; i <= nodeCount; i++) {
if (!weights.hasOwnProperty(i)) {
solution.push(-1);
}
else if (weights[i] !== 0) {
solution.push(weights[i]);
}
}
return solution.join(' ');
}
function initGraph(nodeCount) {
var graph = {};
for (var i = 1; i <= nodeCount; i++) {
graph[i] = [];
}
return graph;
}
function parseEdges(graph, edges) {
for (var i = 0; i < edges.length; i += 2) {
var a = edges[i];
var b = edges[i+1];
graph[a].push(b);
graph[b].push(a);
}
}
function solveTestcase(nodeCount, edges, start) {
var graph = initGraph(nodeCount);
parseEdges(graph, edges);
var weights = solve(graph, [{node: start, weight: 0}]);
console.log(formatSolution(weights, nodeCount));
}
function processData(input) {
var data = input.split(/\s/).map(Number);
var t = data.shift();
while (data.length) {
var nodeCount = data.shift();
var edgeCount = data.shift();
var edges = data.splice(0, edgeCount * 2);
var start = data.shift();
// console.log({nodeCount: nodeCount, edgeCount: edgeCount, edges: edges.length, start: start})
solveTestcase(nodeCount, 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);
});Breadth First Search: Shortest Reach Python Solution
import sys
from pprint import pprint
def print_result(result, start):
res = ''
for i in range(len(result)):
if i != start-1:
res += str(result[i]) + ' '
return res
def calculate(graph, n_of_nodes, start):
visited = [False for i in range(n_of_nodes)]
result = [-1 for i in range(n_of_nodes)]
nodes = []
nodes.append((start,0))
while(len(nodes) > 0):
current = nodes.pop(0)
if visited[current[0]-1]:
continue
visited[current[0]-1] = True
node = graph.get(current[0])
if node != None:
for adjacent in node:
nodes.append((adjacent,current[1]+6))
#if current != start:
if (current[0] != start):
result[current[0]-1] = current[1]
return result
def add_node(graph, node1, node2):
node = graph.get(node1)
if node != None:
node.add(node2)
else:
graph[node1] = set()
graph[node1].add(node2)
file = sys.stdin
number_of_test = int(file.readline())
for i in range(number_of_test):
graph = {}
nodes, edges = file.readline().split(' ')
nodes = int(nodes)
edges = int(edges)
for j in range(edges):
node1, node2 = file.readline().split(' ')
node1 = int(node1)
node2 = int(node2)
node = graph.get(node1)
add_node(graph, node1, node2)
add_node(graph, node2, node1)
start = int(file.readline())
#pprint(graph)
result = calculate(graph, nodes, start)
print(print_result(result, start))