Problem overview
BfsMinDistance(n, edges) works on an unweighted graph with vertices 0 to n - 1. It returns an array dist of length n, where dist[i] is the smallest 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, and vertices 3 and 4 are two edges away, through 1 and 2 respectively.
Approach: breadth-first search
Breadth-first search (BFS) explores a graph in layers. First the source, then every vertex one edge away, then every vertex two edges away, and so on. The first time BFS reaches a vertex is therefore along a shortest path, because all closer vertices were handled before it. This is why BFS, and not depth-first search, is the tool for shortest paths in unweighted graphs.
A queue produces that layer-by-layer order. Vertices come out in the order they went in (first in, first out), so a vertex discovered earlier is processed earlier, and its neighbours are queued behind everything in the current layer.
The distance array does double duty. Filling it with -1 means "not reached yet", so checking minDist[v] == -1 works as the visited test, and the same array holds the final answers. Unreachable vertices keep their -1, which is exactly the value the problem asks for.
Step by step
- Build
graphas aList<List<int>>. Addnempty lists with aforloop, one per vertex, so thatgraph[v]holds the neighbours ofv. - Loop over
edgesand add each edge's second endpoint to the first endpoint's list. This lesson's code records each pair in this one direction. Building the list takesO(m)time formedges. - Create a
Queue<int>and enqueue vertex 0. The search starts there. - Create
minDistwithnew int[n]and fill it with-1usingArray.Fill, since a freshintarray is full of zeros and 0 would look like a real distance. Then setminDist[0] = 0. - Loop while
queue.Count > 0. - Dequeue the front vertex into
node. Taking from the front keeps the layer order. Taking from the back would turn the search into a depth-first one and break the distances. - Loop over the neighbours of
node. - If a neighbour still has distance
-1, give itminDist[node] + 1and enqueue it. Because it is marked at once, no vertex is queued twice. - Return
minDist.
The solution in C#
class Solution {
public int[] BfsMinDistance(int n, int[][] edges) {
List<List<int>> graph = new List<List<int>>();
for (int i = 0; i < n; i++) {
graph.Add(new List<int>());
}
foreach (int[] edge in edges) {
graph[edge[0]].Add(edge[1]);
}
Queue<int> queue = new Queue<int>();
queue.Enqueue(0);
int[] minDist = new int[n];
Array.Fill(minDist, -1);
minDist[0] = 0;
while (queue.Count > 0) {
int node = queue.Dequeue();
foreach (int adjNode in graph[node]) {
if (minDist[adjNode] == -1) {
minDist[adjNode] = minDist[node] + 1;
queue.Enqueue(adjNode);
}
}
}
return minDist;
}
}
Trace the example. The queue starts as [0]. Dequeuing 0 gives distance 1 to vertices 1 and 2, and the queue becomes [1, 2]. Dequeuing 1 gives vertex 3 distance 2. Dequeuing 2 gives vertex 4 distance 2. Vertices 3 and 4 have no unreached neighbours, so the queue empties and the array is [0, 1, 1, 2, 2].
Some C# details:
Queue<T>hasEnqueueto add at the back andDequeueto remove from the front.Countis a property, without parentheses, and is the right emptiness check.Dequeueon an empty queue throwsInvalidOperationException, so the loop condition protects it.Array.Fill(array, value)sets every element at once and avoids a manual loop.- Directed lists. The code adds
graph[edge[0]].Add(edge[1])and nothing else. For the lesson's example this is enough, because every edge points away from vertex 0. For a graph where an edge must be walkable both ways, add a second line,graph[edge[1]].Add(edge[0]);. Without it,edges = [[1,0]]leaves vertex 1 at-1. foreachover aListis fine here because the loop never modifiesgraph[node]. Changing a list while aforeachiterates it throwsInvalidOperationException.
Complexity
Time: O(n + m). Each vertex enters the queue at most once, because it is marked on the way in. So the outer loop runs at most n times. The inner loops together look at each adjacency list entry once, which is at most m entries here (2m if you add both directions).
Space: O(n + m) for the adjacency lists, plus O(n) for the queue and the distance array.
Edge cases and common mistakes
- Unreachable vertices. With
n = 4andedges = [[0,1],[2,3]]the answer is[0, 1, -1, -1]. The vertices 2 and 3 are never enqueued, so they keep the initial-1. - Forgetting the fill. If
minDistkeeps its default zeros, every vertex looks reached. The check== -1never succeeds and nothing beyond the source gets a distance. - Not marking on enqueue. If you set the distance only when a vertex is dequeued, the same vertex can be queued several times by different neighbours.
- Using a stack. Replacing the queue with a
Stack<int>gives depth-first order, and the first path found is not necessarily the shortest. - Cycles. For
edges = [[0,1],[1,2],[0,2],[2,3]]the answer is[0, 1, 1, 2]. Vertex 2 is reached first from 0 directly, at distance 1, so the longer route through 1 is ignored.
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 = 4,edges = [[0,1],[1,2],[0,2],[2,3]]gives[0, 1, 1, 2].