Problem overview
The method bfsMinDistance receives n, the number of vertices labeled 0 to n - 1, and edges, an Array[Array[Int]] of pairs [u, v]. It returns an Array[Int] of length n in which entry i is the fewest edges on a path from vertex 0 to vertex i, or -1 when vertex i can't be reached.
For n = 5 and edges = [[0,1],[0,2],[1,3],[2,4]] the answer is [0, 1, 1, 2, 2]: vertex 0 is at distance 0, vertices 1 and 2 are one edge away, and vertices 3 and 4 are two edges away.
Approach: breadth-first search
A breadth-first search (BFS) explores a graph in layers. First it visits the start vertex, then everything one edge away, then everything two edges away, and so on. Because layers are visited in order, the first time the search reaches a vertex is along a shortest path, so its distance can be written down on the spot and never changes.
A queue produces that order. Vertices leave the queue in the order they entered it (first in, first out), so every vertex of one layer is processed before any vertex of the next layer. Taking from the other end, as a stack does, would give a depth-first search, which does not find shortest distances.
The minDist array does double duty. It holds the answer, and the value -1 marks a vertex that hasn't been reached yet, so no separate visited set is needed. Distances are never negative, so -1 can't be confused with a real distance.
On the example, the adjacency list is 0: [1, 2], 1: [3], 2: [4]. The queue starts as [0]. Processing 0 sets the distances of 1 and 2 to 1 and queues them. Processing 1 sets vertex 3 to 2, and processing 2 sets vertex 4 to 2. Vertices 3 and 4 have no outgoing neighbors, so the queue empties.
Step by step
- Build the adjacency list as an array of
nempty buffers, usingArray.fill(n)(mutable.ArrayBuffer[Int]()). The element expression runs once per slot, so each vertex gets its own buffer. - Loop over
edgesand append the second endpoint to the first endpoint's buffer with+=. This isO(m)formedges. - Create the queue with
mutable.Queue(0), which already holds the source vertex.enqueueadds at the back anddequeueremoves from the front. - Create
minDistwithArray.fill(n)(-1)and setminDist(0)to 0, since the source is zero edges from itself. - Loop while the queue is not empty.
nonEmptyis a property, so it takes no parentheses. Each vertex enters the queue at most once. - Take the front vertex into
nodewithdequeue(). - Loop over its neighbors, naming each
adjNode. Over the whole search this looks at each stored edge once. - Handle unreached neighbors. If
minDist(adjNode)is still-1, set it tominDist(node) + 1and enqueue the neighbor. The-1test means a vertex is labeled only the first time it is reached. - End with
minDistas the last expression. Unreachable vertices keep their-1.
The solution in Scala
class Solution {
def bfsMinDistance(n: Int, edges: Array[Array[Int]]): Array[Int] = {
val graph = Array.fill(n)(mutable.ArrayBuffer[Int]())
for (edge <- edges) {
graph(edge(0)) += edge(1)
}
val queue = mutable.Queue(0)
val minDist = Array.fill(n)(-1)
minDist(0) = 0
while (queue.nonEmpty) {
val node = queue.dequeue()
for (adjNode <- graph(node)) {
if (minDist(adjNode) == -1) {
minDist(adjNode) = minDist(node) + 1
queue.enqueue(adjNode)
}
}
}
minDist
}
}
The Scala details worth a closer look:
- Imports. The code writes
mutable.ArrayBufferandmutable.Queue, so it relies onimport scala.collection.mutable. In a standalone file, add that import at the top. - Edge direction. The loop stores each pair in one direction only, from
edge(0)toedge(1). For the example that gives the same distances as a two-way graph, because every pair already points away from vertex 0. For a graph whose edges work both ways, addgraph(edge(1)) += edge(0)inside the loop. With one direction only,n = 2andedges = [[1, 0]]returns[0, -1]. mutable.Queue(0)is a queue ofIntthat starts with one element. The type is inferred from the argument.Array.fill(n)(-1)builds an array ofncopies of the value-1. AnArrayis mutable and has a fixed size, sominDist(0) = 0works on aval.valversusvar.minDistnever gets reassigned; only its contents change, sovalis right.
Complexity
Let m be the number of edges.
Time: O(n + m). Each vertex enters the queue at most once, and the search scans each vertex's neighbor buffer once.
Space: O(n + m). The adjacency list stores every edge, and minDist and the queue hold at most n entries.
Edge cases and common mistakes
- Unreachable vertices. With
n = 4and the single edge[0, 1], the result is[0, 1, -1, -1]. - A shortcut edge. With edges
[0,1], [1,2], [0,2], [2,3], vertex 2 is first reached directly from 0, so the result is[0, 1, 1, 2]rather than the longer route through 1. - Using a stack instead of a queue. Distances then depend on the order of exploration and can be too large.
- Labeling when dequeuing instead of when enqueueing. A vertex could then enter the queue several times before it is processed.
- Forgetting to set the source. Without
minDist(0) = 0, the neighbors of vertex 0 get distance-1 + 1 = 0, and every distance after that is one too small.
Testing
n = 5,edges = [[0,1],[0,2],[1,3],[2,4]]gives[0, 1, 1, 2, 2].n = 4,edges = [[0,1]]gives[0, 1, -1, -1].n = 4,edges = [[0,1],[1,2],[0,2],[2,3]]gives[0, 1, 1, 2].
