# BFS: Shortest Reach in a Graph

# BFS: Shortest Reach in a Graph

piyush121 + 12 comments Here is my Adjacency list based standard BFS solution (in Java 7) for your reference though I recommend reading only when you've spent a good amount of time on this problem.

public static class Graph { List<List<Integer>> adjLst; int size; public Graph(int size) { adjLst = new ArrayList<>(); this.size = size; while(size-- > 0)//Initialize the adjancency list. adjLst.add(new ArrayList<Integer>()); } public void addEdge(int first, int second) { adjLst.get(first).add(second); adjLst.get(second).add(first); // For undirected graph, you gotta add edges from both sides. } public int[] shortestReach(int startId) { // 0 indexed int[] distances = new int[size]; Arrays.fill(distances, -1); // O(n) space. Queue<Integer> que = new LinkedList<>(); que.add(startId); // Initialize queue. distances[startId] = 0; HashSet<Integer> seen = new HashSet<>(); //O(n) space. Could be further optimized. I leave it to you to optimize it. seen.add(startId); while(!que.isEmpty()) { // Standard BFS loop. Integer curr = que.poll(); for(int node : adjLst.get(curr)) { if(!seen.contains(node)) { que.offer(node); // Right place to add the visited set. seen.add(node); // keep on increasing distance level by level. distances[node] = distances[curr] + 6; } } } return distances; } }

joshrbux + 2 comments Thanks, this definitely helped. You actually don't need a set of seen vertices though. If distances[node] == -1, it hasn't been seen yet, and thanks to BFS you'll always visit a node at the earliest possible time. It's still an O(1) check and you save O(n) space.

piyush121 + 0 comments Thanks. I totally agree with your point. But it will still remain a

`O(n) space`

solution. Though, it is always a good idea to use as less space as possible.alessiosalman + 0 comments Yeah, that's exactly what Gary shows in its Hackerrank solve videos on YouTube. Slight optimization there.

Thanks for your code. Actually, the implementation of graphs can vary a lot. This was helpful.

roise0r + 1 comment the requirement says the node ids start from 1, not 0. how did you pass the tests??

joshrbux + 1 comment Check out the indexing in the code provided

ameer_tabony + 0 comments You can create array with extra cell, so the index and ids will be aligned, just need to make sure you start to iterate from index 1 and not 0.

kaozgamer + 0 comments Oh wow I see where I went wrong. My code to increase the distance was outside the loop.

Anyway thanks for sharing your code!

Petronius42 + 1 comment Your comment "For undirected graph, you gotta add edges from both sides" made me realize my mistake, and Boom all tests passing :) Thanks!

popescu_af + 0 comments Haha, your comment about the other comment made me realize the same thing. Thanks!

cocobey73 + 0 comments You can avoid the seen set by using distance since distance[node] != -1 will mean you already traversed that node.

davidnhnd + 1 comment why in this example "1" to "4" is -1? shouldn't it be 12 since "1" -> "2" -> "4"? 4 2 1 2 1 3 1

darshanmodh + 3 comments can anyone explain why List of List is required? Can I store adjLst in array of LinkedList? like

LinkedList<Integer> adj[]; public Graph(int size) { this.size = size; adj = new LinkedList[size]; for(int i=0; i<size; i++) adj[i] = new LinkedList<>(); } public void addEdge(int first, int second) { adj[first].add(second); }

tino1b2be + 0 comments It's not a requirement it's just one way of doing it.

nacho2 + 0 comments Read about different implementations for Graphs and their efficiency depending on the use, in this case using linked lists is enough cause you have to go throught all the data, in other cases maybe you want to find one Node really quick (O(1)) and in that case using matrix representation is better.

Here is some literature :P: Representing graphs

alessiosalman + 0 comments That is also fine, but 2 lists would be probably more readable. I would prefer this:

adj.get(first).add(second)

on this:

adj[first].add(second)

less prone to mistakes.

Anyway, as others have said, there

**many**ways to represent graphs.

Quazar777 + 0 comments you probably forgot to pop the queue.

vicentecneto + 0 comments //For undirected graph, you gotta add edges from both sides.

Thank you very much... I was wondering what was wrong with my code and the problem was that i was adding only one side :)

quocbao100 + 2 comments Here is my solution using Adjacency Matrix

public static class Graph { int size; int[][] adjMatrix; public Graph(int size) { this.size = size; adjMatrix = new int[size][size]; } public void addEdge(int first, int second) { adjMatrix[first][second] = 1; adjMatrix[second][first] = 1; } public int[] shortestReach(int startId) { int[] distances = new int[size]; Arrays.fill(distances, -1); Queue<Integer> queue = new LinkedList<>(); queue.add(startId); distances[startId] = 0; while(!queue.isEmpty()){ int v = queue.remove(); for(int i =0;i<size;i++){ if(adjMatrix[v][i] == 1 && distances[i] == -1 ) { queue.add(i); distances[i] = distances[v]+6; } } } return distances; } }

nkthien + 0 comments cool! you use distances as indicator for node that has been visited which makes the code more compact.

chenming_yong13 + 0 comments Thanks! This is straightforward and easy to understand :)

brachipackter + 0 comments how will it pass when I have node that is connected by 2 pathes to the start node, one is shorthen the other. for example, this input:

1 3 3 1 2 1 3 2 3 1

3 is conneced to 1 (starting point) or directly or by number 2. in your code you move on each path only once, and set the first distance you find. I think you may continue serach for shorter distance. WDYT? am I mising something?

coryliu + 1 comment I wish this problem gave a bit more template to work with, so we could focus on solving the problem rather than building the graph from input first.

kaiserleib + 0 comments It's also pretty maddening that the node ids are 1-indexed.

Sasikrishna + 0 comments Missing start node id :-(

honami_yuya + 2 comments Here is my Python3 solution:

import queue from collections import defaultdict class Graph: def __init__(self, n): self.n = n self.edges = defaultdict(lambda: []) def connect(self,x,y): self.edges[x].append(y) self.edges[y].append(x) def find_all_distances(self, root): distances = [-1 for i in range(self.n)] unvisited = set([i for i in range(self.n)]) q = queue.Queue() distances[root] = 0 unvisited.remove(root) q.put(root) while not q.empty(): node = q.get() children = self.edges[node] height = distances[node] for child in children: if child in unvisited: distances[child] = height + 6 unvisited.remove(child) q.put(child) distances.pop(root) print(" ".join(map(str,distances))) t = int(input()) for i in range(t): n,m = [int(value) for value in input().split()] graph = Graph(n) for i in range(m): x,y = [int(x) for x in input().split()] graph.connect(x-1,y-1) s = int(input()) graph.find_all_distances(s-1)

sriharshaM + 1 comment Can you explain why s-1, x-1, y-1 were passed instead of actual values provided in input?

valbaca + 0 comments The actual node ids input are 1-indexed, such as [1,2,3,4] but it's much easier in code to deal with 0-indexed items like [0,1,2,3]

GeoMatt22 + 1 comment I used a similar approach, with a few minor differences*. Note that

`unvisited`

is redundant, as you can just check`distances < 0`

.(*e.g.

`collections.deque`

for a Queue, and initial distances`[0] + n * [float('inf')]`

to allow 1-based indexing)alessiosalman + 1 comment Yup, same here.

Please @Honami, note that deque is built with performance optimization on popping from both sides, and using lists as queues should be avoided.

kerryjones21 + 0 comments Just wanted to highlight

`using lists as queues should be avoided`

I wrote the code -- perfectly, using lists as a queue. Failed Test Case 5 (ran out of time).

Reimplemented using

`queue`

library and it worked.

hadeer_khalifa44 + 0 comments Are the test cases missing the start node id ?

tangshao28 + 2 comments #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <unordered_set> using namespace std; class Graph { public: vector<int> *adj; int V; Graph(int V) { this->V = V; adj = new vector<int>[V]; } void add_edge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } vector<int> shortest_reach(int start, int n) { vector<int> distances(n,-1); queue<int> que; unordered_set<int> seen; que.push(start); distances[start] = 0; seen.insert(start); while(!que.empty()) { int cur = que.front(); que.pop(); for(int node : adj[cur]) { if (seen.find(node) == seen.end() ) { que.push(node); seen.insert(node); distances[node] = distances[cur] + 6; } } } return distances; } }; int main() { int queries; cin >> queries; for (int t = 0; t < queries; t++) { int n, m; cin >> n; // Create a graph of size n where each edge weight is 6: Graph graph(n); cin >> m; // read and set edges for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; // add each edge to the graph graph.add_edge(u, v); } int startId; cin >> startId; startId--; // Find shortest reach from node s vector<int> distances = graph.shortest_reach(startId, n); for (int i = 0; i < distances.size(); i++) { if (i != startId) { cout << distances[i] << " "; } } cout << endl; } return 0; }

Fixed the code from previous post, it is worth to point out a trivial mistake seen.find(node) != seen.end() should rather be seen.find(node) == seen.end() as revised.

biswajit_mohapa1 + 0 comments is this passing all the test cases

bence_meszaros + 0 comments I really like your solution! Simple and clever. One odd thing for me is that you used an array of vectors instead of a vector of vectors. Another is that you allocated the array on the heap.

supersonic_ht + 1 comment I had to use a try-except block when writing in Python as the 2nd test-test case and the 7th actual test case had no starting index.

skabbit + 1 comment Got exactly the same problem: Input (stdin): 1 6 4 1 2 2 3 3 4 1 5

And no starting index at the end of input, but there is expected output, which is fit to s=0.

ente_alienigena + 0 comments The test cases are not well formed, they are bad input. For example Test case 1 1 70 1988 30 32 50 9 7 58 50 66 38 13 31 67 2 30 14 46 54 34 10 7 25 66 20 18 1 21 49 63 39 20 55 5 3 Says there are 1988 vertexes to read wich is clearely incorrect. Test case 7 is missing the last single int representing the starting node, and so on. Please fix the test cases.

thomas87 + 1 comment This on really got on my nerves. The given source changes the indexing from 1 based to 0 based and also removes the startIdx from the result array for you - so you better not try to take care of that yourself.. The data you get and the data you have to return does not look like what you find in the description at all.

mayonesa + 0 comments can you please elaborate. what you're saying seems crucial but I don't understand.

RodneyShag + 1 comment ### Java solution - passes 100% of test cases

General idea:

1) Figure out how to implement a graph.

2) Uses BFS to find minimum distance of each Node from "start". We can use BFS instead of Dijkstra's algorithm since the edges are all the same weight.import java.util.Scanner; import java.util.HashSet; import java.util.ArrayDeque; public class Solution { private static final int EDGE_WEIGHT = 6; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int numQueries = scan.nextInt(); for (int q = 0; q < numQueries; q++) { int numNodes = scan.nextInt(); int numEdges = scan.nextInt(); /* Create Nodes */ Node [] node = new Node[numNodes + 1]; // node "i" will be at index "i" node[0] = null; for (int i = 1; i <= numNodes; i++) { node[i] = new Node(i); } /* Connect Nodes */ for (int i = 0; i < numEdges; i++) { int n1 = scan.nextInt(); int n2 = scan.nextInt(); node[n1].addNeighbor(node[n2]); } /* Create MST */ int start = scan.nextInt(); findDistances(node[start]); /* Print results */ for (int i = 1; i <= numNodes; i++) { if (i != start) { System.out.print(node[i].distance + " "); } } System.out.println(); } scan.close(); } private static void findDistances(Node start) { if (start == null) { return; } ArrayDeque<Node> deque = new ArrayDeque<>(); // use deque as a queue start.distance = 0; deque.add(start); while (!deque.isEmpty()) { Node curr = deque.remove(); for (Node neighbor : curr.neighbors) { if (neighbor.distance == -1) { // meaning it's unvisited neighbor.distance = curr.distance + EDGE_WEIGHT; deque.add(neighbor); } } } } /* Implementation of an UNDIRECTED graph */ public static class Node { public final int id; // each Node will have a unique ID public int distance; // Also tells us if Node has been visited (-1 means unvisited) public HashSet<Node> neighbors; public Node (int id) { this.id = id; distance = -1; neighbors = new HashSet<>(); } public void addNeighbor(Node neighbor) { neighbors.add(neighbor); neighbor.neighbors.add(this); } @Override public boolean equals(Object other) { if (other == this) { return true; } else if (other == null || !(other instanceof Node)) { return false; } Node otherNode = (Node) other; return this.id == otherNode.id; } @Override public int hashCode() { return id; // simple and effective } } }

From my HackerRank Java solutions.

davidnhnd + 1 comment why in this example "1" to "4" is -1? shouldn't it be 12 since "1" -> "2" -> "4"? 4 2 1 2 1 3 1

RodneyShag + 0 comments I'm assuming you're talking about the sample input in the problem. There is no edge from 1 to 4 as the picture in the problem shows, so it is -1.

Sort 179 Discussions, By:

Please Login in order to post a comment