HackerRank Breadth First Search: Shortest Reach Problem Solution

HackerRank Breadth First Search: Shortest Reach

Yashwant Parihar,

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:

  1. 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].

  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.

HackerRank Breadth First Search: Shortest Reach Problem Solution
HackerRank Breadth First Search: Shortest Reach Problem Solution

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))
c C# C++ HackerRank Solutions java javascript python

Leave a Reply