Problem overview
The method bfsMinDistance receives n, the number of vertices labeled 0 to n - 1, and a list of edges, where each [u, v] connects two vertices. It returns an array dist of length n. Entry dist[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 answer is [0, 1, 1, 2, 2]. Vertex 0 is at distance 0 from itself. Vertices 1 and 2 are one edge away. Vertices 3 and 4 are two edges away, through 1 and 2 respectively.
Approach: expand outward one layer at a time
All edges count the same, so the vertices at distance 1 are the neighbors of vertex 0, the vertices at distance 2 are the not-yet-seen neighbors of those, and so on. Breadth-first search (BFS) walks the graph exactly in this order, using a queue: vertices are removed from the front and newly found vertices are added to the back, so every vertex at distance d is processed before any vertex at distance d + 1.
The distance array doubles as the visited marker. It starts filled with -1. The first time BFS reaches a vertex, it must be along a shortest path, so the distance is final: set it to the distance of the vertex we came from plus one, and put the vertex in the queue. A vertex that already has a distance is never touched again. Vertices that BFS never reaches keep their -1, which is exactly the required answer for unreachable vertices.
As a comparison, depth-first search would also visit every connected vertex, but it follows one long path first and doesn't produce shortest distances. The queue order is what makes BFS correct here.
Step by step
- Build the adjacency list.
graphholds one empty[Int]per vertex, so a vertex's neighbors can be looked up directly. - Fill it from
edges. Loop over the edges and append each edge's second endpoint to the first endpoint's array. - Create the queue as an array holding only vertex 0. Appending adds to the back and
removeFirsttakes from the front. - Create
minDistfilled with-1, then setminDist[0]to 0. - Loop while the queue isn't empty.
isEmptyis a property, so it has no parentheses. - Take the front vertex into
nodewithremoveFirst. Taking from the back would turn the search into a depth-first one. - Loop over each neighbor
adjNodeofnode. - If the neighbor is still
-1, set its distance tominDist[node] + 1and enqueue it. - Return
minDist.
The solution in Swift
class Solution {
func bfsMinDistance(_ n: Int, _ edges: [[Int]]) -> [Int] {
var graph = [[Int]](repeating: [], count: n)
for edge in edges {
graph[edge[0]].append(edge[1])
}
var queue = [0]
var minDist = [Int](repeating: -1, count: n)
minDist[0] = 0
while !queue.isEmpty {
let node = queue.removeFirst()
for adjNode in graph[node] {
if minDist[adjNode] == -1 {
minDist[adjNode] = minDist[node] + 1
queue.append(adjNode)
}
}
}
return minDist
}
}
The Swift details worth a closer look:
- Edges are stored in one direction only. The loop that builds
graphappendsedge[1]tograph[edge[0]]and does nothing for the reverse. So this solution follows each edge from its first endpoint to its second. With the lesson's example that gives the right answer, but a graph that is truly undirected needs a second line,graph[edge[1]].append(edge[0]). Forn = 4and[[1,0],[2,1]], the code as written returns[0, -1, -1, -1]. - An array as a queue. Swift has no built-in queue.
removeFirst()on an array shifts every remaining element, so it costsO(n)for a long queue. For the lesson's sizes that is fine. For larger graphs, keep the queue in an array and move an integer head index forward instead of removing. [Int](repeating: -1, count: n)builds an array ofncopies of-1. For the adjacency list,[[Int]](repeating: [], count: n)works the same way, and the empty arrays are independent because arrays are values.- Type inference.
var queue = [0]is inferred as[Int], so appending integers works with no annotation. let node = queue.removeFirst()both removes the element and returns it, so one line takes the front.
Complexity
Let V be the number of vertices and E the number of edges.
Time: O(V + E) in the BFS logic. Each vertex enters the queue at most once, because the -1 check blocks repeat visits, and each vertex's neighbor list is scanned once. The array-based queue adds a cost for removeFirst, which makes the worst case O(V² + E).
Space: O(V + E). The adjacency list holds E entries, and the distance array and the queue hold at most V.
Edge cases and common mistakes
- Unreachable vertices. With
n = 4and[[0,1],[2,3]], the result is[0, 1, -1, -1]. - Cycles. A triangle
[[0,1],[1,2],[2,0]]gives[0, 1, 2]with one direction stored. The-1check stops the search from going around. - Treating the graph as undirected. Edges listed as
[1, 0]have no effect from vertex 0 with the code above, as described earlier. - Using a stack instead of a queue. Taking from the back gives some path, not the shortest one.
- Marking vertices when they are dequeued. A vertex could then enter the queue several times. Setting the distance when it is enqueued prevents that.
- Forgetting the source's distance. If
minDist[0]stayed at-1, the search from the neighbors would treat vertex 0 as unvisited and enqueue it again.
Testing
n = 5,[[0,1],[0,2],[1,3],[2,4]]gives[0, 1, 1, 2, 2].n = 4,[[0,1],[2,3]]gives[0, 1, -1, -1].n = 3,[[0,1],[1,2],[2,0]]gives[0, 1, 2].
