Problem overview
The function bfsMinDistance receives n, the number of vertices labeled 0 to n - 1, and edges, an Array<IntArray> of pairs [u, v]. It returns an IntArray of length n in which entry i is the minimum number of 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 result is [0, 1, 1, 2, 2]. Vertex 0 is at distance 0 from itself, vertices 1 and 2 are one edge away, and vertices 3 and 4 are two edges away, through 1 and 2.
Approach: breadth-first search
Breadth-first search (BFS) explores a graph in rings. First it visits the start vertex, then everything one edge away, then everything two edges away, and so on. Because of that order, the first time BFS reaches a vertex is along a shortest path, in an unweighted graph where every edge counts as 1. So the first distance written for a vertex is its final answer, and no vertex is ever updated twice.
The ring order comes from a queue. Vertices leave the queue in the order they entered it, so every vertex at distance d is processed before any vertex at distance d + 1. Taking vertices from the wrong end of the queue would give depth-first order, and the distances would come out wrong.
The distance array doubles as the record of visited vertices. It starts filled with -1, meaning "not reached yet". When BFS meets a neighbour whose entry is still -1, it writes the distance and enqueues the neighbour. Anything BFS never reaches keeps -1, which is exactly what the problem wants for unreachable vertices.
The function also needs fast neighbour lookup, so it first turns the list of edges into an adjacency list: for every vertex, the list of vertices it leads to.
Step by step
- Create the adjacency list.
graphis an array ofnempty mutable lists, one per vertex. TheArray(n) { ... }constructor runs its lambda once per index, so each vertex gets its own list. - Fill it from
edges. For eachedge, addedge[1]to the list ofedge[0]. This takes time proportional to the number of edges. - Create the queue as an
ArrayDequeand put vertex 0 in it. Adding goes to the back andremoveFirsttakes from the front, both in constant time. - Create
minDistas anIntArrayof sizenfilled with-1, then setminDist[0]to 0 because the start is zero edges from itself. - Loop while the queue is not empty. Each vertex enters the queue at most once, so the loop runs at most
ntimes. - Take the front vertex into
nodewithremoveFirst. - Loop over its neighbours, calling each one
adjNode. Across the whole search this looks at every stored edge once. - Handle unreached neighbours only. If
minDist[adjNode]is-1, set it tominDist[node] + 1and enqueueadjNode. - Return
minDist.
The solution in Kotlin
class Solution {
fun bfsMinDistance(n: Int, edges: Array<IntArray>): IntArray {
val graph = Array(n) { mutableListOf<Int>() }
for (edge in edges) {
graph[edge[0]].add(edge[1])
}
val queue = ArrayDeque<Int>()
queue.add(0)
val minDist = IntArray(n) { -1 }
minDist[0] = 0
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
for (adjNode in graph[node]) {
if (minDist[adjNode] == -1) {
minDist[adjNode] = minDist[node] + 1
queue.add(adjNode)
}
}
}
return minDist
}
}
The Kotlin details worth a closer look:
IntArray(n) { -1 }creates a primitive int array whose every element is the lambda's result. Without the lambda,IntArray(n)would be filled with 0, which would wrongly say "distance 0" for every vertex.Array(n) { mutableListOf<Int>() }runs the lambda once per index, givingnseparate lists. The array's type isArray<MutableList<Int>>.ArrayDequeis Kotlin's own double-ended queue.addappends at the back,removeFirst()takes from the front, andisNotEmpty()drives the loop.- Edge direction in this code. Only
graph[edge[0]].add(edge[1])is executed, so the search follows each edge from its first endpoint to its second. For an edge to work in both directions, the loop also needsgraph[edge[1]].add(edge[0]). With the code as given,n = 3andedges = [[1, 0], [1, 2]]returns[0, -1, -1], because nothing leads out of vertex 0. val nodeis a fresh read-only value in each iteration, while the arrays and lists it indexes remain mutable.
Complexity
Time: O(n + m), where m is the number of edges. Building the lists costs O(n + m). In the search, each vertex is enqueued at most once and each stored edge is examined once.
Space: O(n + m). The adjacency list holds one entry per stored edge, and the distance array and queue hold at most n entries each.
Edge cases and common mistakes
- Unreachable vertices. With
n = 5andedges = [[0, 1], [2, 3]]the result is[0, 1, -1, -1, -1]. Vertices 2, 3 and 4 are never enqueued, so they keep-1. - No edges. With
n = 2and no edges the result is[0, -1]. The start always has distance 0. - Cycles. In a triangle such as
[[0, 1], [1, 2], [2, 0]], vertex 0 already has distance 0, so the edge back to it is ignored and the search can't loop forever. The distances come out as[0, 1, 2]. - Shortcuts. For
n = 4and[[0, 1], [1, 2], [0, 2], [2, 3]], vertex 2 gets distance 1 through the direct edge, not 2 through vertex 1, and vertex 3 gets 2. The result is[0, 1, 1, 2]. - Using a stack instead of a queue. Removing from the back visits vertices in depth-first order, and the first distance written is no longer the shortest.
- Checking for visited after the fact. Marking a vertex when it is enqueued, not when it is dequeued, keeps the queue free of duplicates.
- Initialising with 0. A zero-filled array can't tell "unreached" from "distance 0".
Testing
n = 5,[[0, 1], [0, 2], [1, 3], [2, 4]]gives[0, 1, 1, 2, 2].n = 5,[[0, 1], [2, 3]]gives[0, 1, -1, -1, -1].n = 4,[[0, 1], [1, 2], [0, 2], [2, 3]]gives[0, 1, 1, 2].n = 4,[[0, 1], [1, 2], [2, 0]]gives[0, 1, 2, -1].n = 2, no edges, gives[0, -1].