Start learning free

LESSON 331 OF 343 · GRAPHS

BFS Min Distance to Every Vertex in C++: Queue and Adjacency Map

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
    Ctrl + Enter to check

    C++ · GRAPHS

    Bfs Min Distance To Every Vertex in C++, explained

    Problem overview

    The method bfsMinDistance receives the number of vertices n, labelled 0 to n - 1, and a vector edges of pairs [u, v]. It returns a vector dist of length n in which dist[i] is the smallest number of edges on a route from vertex 0 to vertex i, or -1 when no route exists.

    For 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, and vertices 3 and 4 are two edges away. The answer is [0, 1, 1, 2, 2].

    Approach: breadth-first search

    All edges count the same, so the nearest vertices are the ones reachable in one step, then the ones reachable in two, and so on. Breadth-first search (BFS) visits vertices in exactly that order, in rings around the source: distance 0, then distance 1, then 2.

    The tool that produces this order is a queue, a first-in, first-out line. Start with the source in the queue. Repeatedly take the vertex at the front, look at its neighbours, and add every neighbour not seen before to the back. Vertices discovered earlier sit nearer the front and are processed first, so all vertices at distance d come out before any at distance d + 1.

    That order gives the key property: the first time BFS reaches a vertex, it has taken a shortest route. So the distance can be written down immediately and never changed. The dist vector doubles as the visited record: a value of -1 means "not reached yet".

    On the example, the queue goes: [0]. Take 0 and reach 1 and 2 (distance 1) giving [1, 2]. Take 1 and reach 3 (distance 2). Take 2 and reach 4 (distance 2). Then 3 and 4 have no new neighbours and the queue empties.

    Step by step

    1. Build the adjacency list graph as an unordered_map<int, vector<int>>, mapping each vertex to its neighbours. The first use of graph[x] creates an empty vector for x, so there's no setup loop.
    2. Fill it from edges. Loop with auto& edge and push edge[1] onto graph[edge[0]]. This code records each pair in one direction, from edge[0] to edge[1].
    3. Create the queue q as a queue<int> and push the source, 0.
    4. Create minDist with n entries of -1, then set minDist[0] to 0, because the source is zero edges from itself.
    5. Loop while the queue is not empty.
    6. Take the next vertex: read q.front() into node, then call q.pop(). Two calls are needed because pop returns nothing.
    7. Visit its neighbours with a range-based loop over graph[node], naming each one adjNode.
    8. Claim unreached neighbours. If minDist[adjNode] is still -1, set it to minDist[node] + 1 and push adjNode onto the queue. The -1 test means a vertex enters the queue at most once.
    9. Return minDist. Vertices that BFS never reached keep their -1.

    The solution in C++

    class Solution {
public:
    vector<int> bfsMinDistance(int n, vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> graph;
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }
        queue<int> q;
        q.push(0);
        vector<int> minDist(n, -1);
        minDist[0] = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int adjNode : graph[node]) {
                if (minDist[adjNode] == -1) {
                    minDist[adjNode] = minDist[node] + 1;
                    q.push(adjNode);
                }
            }
        }
        return minDist;
    }
};

    The C++ details to notice:

    • unordered_map::operator[] inserts. Reading graph[node] for a key that is missing creates an empty vector and returns it. That is what makes the push-back loop work without setup, and it also makes the neighbour loop safe for a vertex with no outgoing edges. The price is that a plain lookup can grow the map. When you only want to check, use find or count. A vector<vector<int>> of size n would also work, and it is faster.
    • vector<int> minDist(n, -1) uses the constructor that takes a size and a fill value, so no loop is needed.
    • front() then pop(). std::queue keeps reading and removing apart. Copy the front value into node before you pop, since the reference returned by front() is not valid after the pop.
    • Direction of edges. The code adds only edge[0] → edge[1]. That matches the example, where each edge is listed with the nearer vertex first. To treat every edge as two-way, which is what an undirected graph needs, add a second line inside the loop: graph[edge[1]].push_back(edge[0]);. With that line, the example still gives [0, 1, 1, 2, 2], and an input like n = 3, edges = [[1,0]] gives [0, 1, -1] instead of [0, -1, -1].
    • Index types. n and the vertices are int, so minDist[adjNode] indexes the vector with an int. That's fine for non-negative values.

    Complexity

    Time: O(n + m), where m is the number of edges. Building the map touches each edge once. Each vertex enters the queue at most once, and the neighbour loops scan each stored edge once in total.

    Space: O(n + m). The adjacency map holds every stored edge, and minDist and the queue each hold at most n vertices.

    Edge cases and common mistakes

    • The source itself. minDist[0] must be set to 0 before the loop, or the source would look unreached and could be queued again.
    • Unreachable vertices. They keep -1, which is the required answer. Initialising the vector with 0 instead would make them look like they were at the source.
    • Using a stack instead of a queue. That gives depth-first order, and the first route found is often not the shortest.
    • Setting the distance when popping. Marking vertices only when they leave the queue lets the same vertex be pushed several times. Set the distance at the moment of pushing.
    • Cycles. A vertex reached again is skipped, because its distance is no longer -1, so cycles can't cause an endless loop.
    • Isolated source. If vertex 0 has no neighbours, the loop runs once and the result is 0 followed by -1 entries.

    Testing

    • n = 5, edges = [[0,1],[0,2],[1,3],[2,4]] gives [0, 1, 1, 2, 2].
    • n = 3, edges = [[0,1]] gives [0, 1, -1].
    • With the extra reverse-edge line added, n = 3, edges = [[1,0]] gives [0, 1, -1].
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free