Problem overview
The method bfsMinDistance receives the number of vertices n, labeled 0 to n - 1, and a list of edges, each a pair [u, v]. It returns a list dist of length n, where dist[i] is the minimum number of edges on a path from vertex 0 to vertex i, or -1 if vertex i can't be reached.
In the example, n = 5 and edges = [[0, 1], [0, 2], [1, 3], [2, 4]]. Vertex 0 is at distance 0. Vertices 1 and 2 are one edge away. Vertices 3 and 4 are two edges away, through 1 and 2. The result is [0, 1, 1, 2, 2].
Approach: explore the graph in layers
In an unweighted graph, every edge counts as 1, so the shortest distance is the smallest number of edges. Breadth-first search (BFS) finds it by exploring in layers: first the source, then everything one edge away, then everything two edges away, and so on. The first time the search reaches a vertex, it has used as few edges as possible, so that distance is final.
The layers come from a queue, where items leave in the order they arrived (first in, first out). The search takes a vertex from the front, looks at its neighbors, and adds every newly found neighbor to the back. Vertices of the current layer are all in front of the vertices of the next layer, so the layers are processed in order.
To know which vertices are new, the distance list does double duty. It starts with -1 everywhere, meaning not reached yet. A vertex is new exactly when its entry is still -1, so no separate visited set is needed. Each vertex is queued at most once.
On the example: the queue starts as [0]. Taking 0 finds the neighbors 1 and 2, which get distance 1. Taking 1 finds 3, which gets distance 2. Taking 2 finds 4, with distance 2. Taking 3 and 4 finds nothing new, and the queue empties.
Step by step
- Build the adjacency list.
graphis a list ofnempty lists, one per vertex, sograph[i]holds the neighbors of vertexi. Because the size is known, a list is simpler than a dictionary. - Fill it from
edges. For eachedge, appendedge[1]to the listgraph[edge[0]]. - Create the queue as a
dequethat holds only the source vertex 0. - Create
minDistwithnentries of-1, then setminDist[0]to 0, because the source is zero edges away from itself. - Loop while the queue is not empty. An empty deque counts as false, so
while queue:is enough. - Take the front vertex into
nodewithpopleft(). - Visit each neighbor
adj_nodeingraph[node]. - Handle only new vertices. If
minDist[adj_node] == -1, set it tominDist[node] + 1and append the vertex to the queue. - Return
minDist. Vertices the search never reached keep their-1.
The solution in Python
class Solution:
def bfsMinDistance(self, n: int, edges: List[List[int]]) -> List[int]:
graph = [[] for _ in range(n)]
for edge in edges:
graph[edge[0]].append(edge[1])
queue = deque([0])
minDist = [-1] * n
minDist[0] = 0
while queue:
node = queue.popleft()
for adj_node in graph[node]:
if minDist[adj_node] == -1:
minDist[adj_node] = minDist[node] + 1
queue.append(adj_node)
return minDist
The Python details worth a closer look:
- Why a comprehension for the buckets.
[[] for _ in range(n)]createsnseparate lists. Writing[[]] * nwould repeat one listntimes, so appending tograph[0]would appear in every bucket. - Why
[-1] * nis fine. Repeating an integer is safe because integers can't be changed in place. AssigningminDist[0] = 0replaces one slot and leaves the others alone. dequeinstead of a list.deque.popleft()takes constant time.list.pop(0)shifts every remaining item, which costsO(n)per removal. A deque comes fromcollections; the lesson's file already imports it.deque([0]). The argument is an iterable, so the list[0]supplies the first item.deque(0)would raise aTypeError, since an integer can't be iterated.- Edges are recorded in one direction. The code appends
edge[1]tograph[edge[0]]only, so each pair is an edge from its first vertex to its second. Treating an edge as two-way takes one more line,graph[edge[1]].append(edge[0]). The lesson's tests pass with the code as shown, and the example behaves the same either way.
Complexity
Time: O(n + m), where m is the number of edges. Building the adjacency list takes O(n + m). Each vertex enters the queue at most once, and when it is taken out, the inner loop goes over its neighbor list. Across the whole search, that loop runs once per stored edge.
Space: O(n + m). The adjacency list holds the edges, and the distance list and the queue each hold at most n entries.
Edge cases and common mistakes
- Unreachable vertices. A vertex with no connection from 0 stays at
-1. Withn = 4andedges = [[0, 1], [2, 3]], the answer is[0, 1, -1, -1]. - Cycles. The
-1check stops the search from re-adding vertices already reached, so a triangle like[[0, 1], [1, 2], [2, 0]]doesn't loop. - Taking from the wrong end. Using
pop()instead ofpopleft()takes the newest vertex first. That is a depth-first order, and the distances it records can be too large. - Updating a distance twice. Overwriting an existing distance can replace a shortest distance with a longer one. Only the first arrival counts.
- Setting the source. If
minDist[0]stays-1, the source looks unreached and can be queued again by a neighbor. Set it to 0 before the loop. - Shared lists. Using
[[]] * nfor the adjacency list mixes up all the neighbor lists.
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 = 3,edges = [[0, 1], [1, 2], [2, 0]]gives[0, 1, 2].n = 3,edges = [[0, 1], [0, 2], [1, 2]]gives[0, 1, 1].