Problem overview
The function bfs_min_distance receives the number of vertices n (labeled 0 to n - 1) and a vector of edges, where each edge is a pair [u, v]. It returns a vector of length n whose entry i is the smallest number of edges on a walk 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 0 steps 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
All edges count the same, so the distance to a vertex is just the fewest edges on any route to it. Breadth-first search finds those routes in order of length. It first visits vertex 0, then everything one edge away, then everything two edges away, and so on, like ripples spreading from a stone dropped in water.
A queue produces that order. Vertices are taken from the front, and newly discovered neighbors go to the back, so every vertex at distance d is processed before any vertex at distance d + 1. The first time the search reaches a vertex is therefore along a shortest route, and its distance never needs to change.
An array of distances doubles as the "visited" record. It starts filled with -1, meaning "not reached yet", so a vertex whose entry is still -1 has not been discovered.
On the example: 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. Processing 3 and 4 finds no new neighbors, and the queue empties.
Step by step
- Build the adjacency list
graphas a mutableVec<Vec<i32>>ofnempty vectors. The count must be ausize, so it is writtenn as usize. - Fill it from
&edges. For eachedge, pushedge[1]onto the list at indexedge[0] as usize. Borrowing&edgesmeans the vector isn't consumed. - Create the queue as a
VecDeque<i32>and push the source, vertex 0, onto the back withpush_back. - Create
min_distwithvec![-1i32; n as usize]and setmin_dist[0]to 0. Thei32suffix makes the element type match the return type. - Loop while the queue is not empty. Each vertex enters the queue at most once, so this loop runs at most
ntimes. - Take the front vertex with
pop_front().unwrap().pop_frontreturns anOption, and the loop condition guarantees it isSome. - Loop over its neighbors with
for &adj_node in &graph[node as usize]. - Process a neighbor only if its distance is still
-1. Set it to the current vertex's distance plus one and push it onto the queue. - Return
min_dist. Any vertex that was never reached keeps its-1.
The solution in Rust
use std::collections::VecDeque;
impl Solution {
fn bfs_min_distance(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
let mut graph: Vec<Vec<i32>> = vec![Vec::new(); n as usize];
for edge in &edges {
graph[edge[0] as usize].push(edge[1]);
}
let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(0);
let mut min_dist = vec![-1i32; n as usize];
min_dist[0] = 0;
while !queue.is_empty() {
let node = queue.pop_front().unwrap();
for &adj_node in &graph[node as usize] {
if min_dist[adj_node as usize] == -1 {
min_dist[adj_node as usize] = min_dist[node as usize] + 1;
queue.push_back(adj_node);
}
}
}
min_dist
}
}
The Rust details worth a closer look:
VecDequeis a double-ended queue fromstd::collections.push_backandpop_frontboth take constant time. A plainVecwould make removing from the front slow, because every remaining element shifts.- Edge direction. The loop records each edge from
edge[0]toedge[1]only. If an edge should be usable both ways, add a second line,graph[edge[1] as usize].push(edge[0]);. Forn = 3andedges = [[1,0],[1,2]], the code as written returns[0, -1, -1], and with the extra line it returns[0, 1, 2]. - Casts. Vertices are
i32values, but only ausizecan index a vector, so every index is writtenx as usize. - Pattern
&adj_node. Looping over a borrowed vector gives&i32items. The&in the pattern copies the number out, soadj_nodeis a plaini32. vec![-1i32; n as usize]repeats a value, whilevec![Vec::new(); n as usize]clones the empty vector, giving each vertex its own list.
Complexity
Time: O(n + m), where m is the number of edges. Building the lists takes O(m). Each vertex is queued once, and over the whole search each adjacency list is scanned once.
Space: O(n + m). The adjacency list stores every edge, and the queue and the distance vector hold at most n entries.
Edge cases and common mistakes
- Unreachable vertices. For
n = 4andedges = [[0,1],[2,3]]the answer is[0, 1, -1, -1]. The group {2, 3} is never touched. - Cycles. In
[[0,1],[1,2],[0,2],[2,3]], vertex 2 is reached directly from 0 and also through 1. The distance is set once, to 1, and the check against-1stops the second route from overwriting it. - Using a stack instead of a queue. Taking vertices from the back follows deep routes first, and the first route found to a vertex is no longer the shortest.
- Marking vertices when they are taken out of the queue rather than when they are put in. A vertex can then be queued many times by different neighbors.
- Forgetting to set
min_dist[0] = 0. The source would stay at-1, and its neighbors would get distance 0.
Testing
n = 5,edges = [[0,1],[0,2],[1,3],[2,4]]gives[0, 1, 1, 2, 2].n = 4,edges = [[0,1],[2,3]]gives[0, 1, -1, -1].n = 5,edges = [[0,1],[1,2],[0,2],[2,3]]gives[0, 1, 1, 2, -1].
