LESSON 327 OF 338 · GRAPHS

BFS Min Distance to Every Vertex in Go: Queue-Based Search

Practice BFS, O(V+E) Read the full explanation

Given an unweighted undirected graph with n vertices (labeled 0 to n-1) and a list of edges where edges[i] = [u, v], find the minimum distance (number of edges) from vertex 0 to every other vertex using BFS.

Return an array dist of length n where dist[i] is the minimum distance from vertex 0 to vertex i. Use -1 if a vertex is unreachable.

Example

Input: n = 5, edges = [[0,1],[0,2],[1,3],[2,4]]
Output: [0, 1, 1, 2, 2]
Explanation:
- 0 → 0: distance 0
- 0 → 1: distance 1
- 0 → 2: distance 1
- 0 → 1 → 3: distance 2
- 0 → 2 → 4: distance 2

Constraints

2 <= n <= 1000
1 <= edges.length <= 5000
0 <= u, v < n
No self-loops or duplicate edges.

STEP 1 OF 9

Guided

Ctrl + Enter to check

Bfs Min Distance To Every Vertex in Go, explained

Problem overview

The function bfsMinDistance receives the number of vertices n (labeled 0 to n - 1) and a list of edges. It returns a slice 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, 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

Distances in an unweighted graph come naturally from breadth-first search (BFS). It explores the graph in layers: first the start, then everything one edge away, then everything two edges away, and so on. The first time the search reaches a vertex, it has taken the fewest edges possible, so that is the vertex's distance and it never needs to change.

A queue produces the layering. Vertices leave the queue in the order they entered it (first in, first out), so every vertex at distance d is processed before any vertex at distance d + 1. When a vertex is processed, each neighbor not seen before gets distance distance[node] + 1 and joins the back of the queue.

The -1 in the answer does double duty. Every entry starts as -1, meaning "not reached yet", and a vertex the search never touches keeps it. That is exactly the value required for unreachable vertices, so the distance slice also serves as the visited record.

Step by step

Create the adjacency list graph as make([][]int, n), so each vertex's neighbors can be looked up by index.
Loop over edges and append each edge's second vertex to the first vertex's list. Remember to assign the result of append back.
Create the queue as a slice holding just vertex 0.
Create minDist with make, set every entry to -1 in a loop (a new slice is zero-filled, and 0 would wrongly mean "at distance 0"), then set minDist[0] = 0.
Loop while len(queue) > 0. Go has no while; a for with only a condition plays that role.
Pop the front: copy queue[0] into node, then reslice with queue = queue[1:].
Range over graph[node], naming each neighbor adjNode.
If minDist[adjNode] == -1, the vertex is new. Set it to minDist[node] + 1 and append it to the queue.
Return minDist.

The solution in Go

func bfsMinDistance(n int, edges [][]int) []int {
    graph := make([][]int, n)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    queue := []int{0}
    minDist := make([]int, n)
    for i := range minDist {
        minDist[i] = -1
    }
    minDist[0] = 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, adjNode := range graph[node] {
            if minDist[adjNode] == -1 {
                minDist[adjNode] = minDist[node] + 1
                queue = append(queue, adjNode)
            }
        }
    }
    return minDist
}

The Go details worth knowing:

A slice works as a queue. append adds at the back, and queue = queue[1:] drops the front by moving the slice's start forward. No elements are copied, so each operation is cheap. The popped value's memory stays in the underlying array until the slice is reallocated, which is harmless at this size.
The edge direction. The code records each pair once, as a connection from edge[0] to edge[1]. For edges that are listed with the smaller vertex first, as in the example, that is all that is needed. With n = 3 and edges [[1,0],[2,1]], however, vertex 0 has no outgoing connection, so the result is [0, -1, -1]. To treat every edge as two-way, also append edge[0] to graph[edge[1]]; with that extra line, the same edges give [0, 1, 2].
for i := range minDist loops over the indices only, which is what the initialization loop needs.
[]int{0} is a slice literal with one element. queue is an []int of vertex labels.

Complexity

Building the adjacency list takes O(E) for E edges. Each vertex enters the queue at most once, because the -1 check blocks repeats, and each adjacency entry is examined once. BFS is therefore O(V + E) in time. The adjacency list, the queue and minDist take O(V + E) space.

Edge cases and common mistakes

Unreachable vertices. With n = 4 and edges [[0,1],[2,3]] the result is [0, 1, -1, -1]. Vertices 2 and 3 are never enqueued, so they keep -1.
Cycles and shortcuts. With edges [[0,1],[1,2],[0,2],[2,3]] the result is [0, 1, 1, 2]. Vertex 2 gets distance 1 straight from 0. Since the check skips vertices that already have a distance, the longer route through 1 can't overwrite it.
Leaving the initial values at 0. A zero-filled slice cannot tell "distance 0" from "not visited", and vertices could be processed twice.
Setting the distance when popping instead of when pushing. A vertex may be enqueued several times before it is popped. Assigning the distance at push time prevents that.
Using a stack instead of a queue. Popping from the back gives depth-first order, and the recorded distances would no longer be minimal.

Testing

n = 5, edges [[0,1],[0,2],[1,3],[2,4]] returns [0 1 1 2 2].
n = 4, edges [[0,1],[2,3]] returns [0 1 -1 -1].
n = 4, edges [[0,1],[1,2],[0,2],[2,3]] returns [0 1 1 2].

Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free