We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- BFS: Shortest Reach in a Graph
- Discussions

# BFS: Shortest Reach in a Graph

# BFS: Shortest Reach in a Graph

+ 18 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; } }

+ 2 comments 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.

+ 5 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)

+ 0 comments Missing start node id :-(

+ 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.

Load more conversations

Sort 296 Discussions, By:

Please Login in order to post a comment