HackerRank Breadth First Search: Shortest Reach Yashwant Parihar, May 14, 2023May 14, 2023 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. ExampleThe following graph is based on the listed inputs: n = 5 // number of nodesm = 3 // number of edgesedges = [1, 2], [1, 3], [3, 4]8 = 1 // starting nodeAll 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 DescriptionComplete 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 Returnsint[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, and4 (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. 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 CcppCSharpHackerrank Solutionsjavajavascriptpython