Breadth-first search (BFS)

Breadth-first search (BFS) explores a graph outward from a start vertex in layers. It uses a FIFO queue: vertices discovered first are processed first. On an unweighted graph (or one where every edge has equal cost), the first time BFS reaches a vertex gives the minimum number of edges from the start, provided the search tracks distances or parents.

Work through a graph

Visited: –

Queue: –

PreviousNext stepReset

Neighbors are considered alphabetically. DFS pushes them in reverse order so the first alphabetical neighbor is visited next.

Choose BFS and start at A. After processing A, its neighbors enter the queue. Each step removes the front item, visits it and enqueues as-yet-undiscovered neighbors. The viewer shows the queue remaining after that step. Edges in the sample are undirected and neighbor order is alphabetical.

Implementation in C# and C++

C#

C# | BFS.cs

using System.Collections.Generic;

static List<int> Bfs(IReadOnlyList<int>[] graph, int start)
{
    if ((uint)start >= (uint)graph.Length)
        throw new ArgumentOutOfRangeException(nameof(start));
    var visited = new bool[graph.Length];
    var queue = new Queue<int>();
    var order = new List<int>();
    visited[start] = true;
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        int current = queue.Dequeue();
        order.Add(current);
        foreach (int next in graph[current])
        {
            if ((uint)next >= (uint)graph.Length)
                throw new ArgumentException("Invalid neighbor index", nameof(graph));
            if (visited[next]) continue;
            visited[next] = true;
            queue.Enqueue(next);
        }
    }
    return order;
}

C++

C++ | BFS.cpp

#include <vector>
#include <queue>
#include <stdexcept>

std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int start) {
    if (start < 0 || static_cast<std::size_t>(start) >= graph.size())
        throw std::out_of_range("start");
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> queue;
    std::vector<int> order;
    visited[start] = true;
    queue.push(start);
    while (!queue.empty()) {
        int current = queue.front(); queue.pop();
        order.push_back(current);
        for (int next : graph[current]) {
            if (next < 0 || static_cast<std::size_t>(next) >= graph.size())
                throw std::out_of_range("neighbor");
            if (visited[next]) continue;
            visited[next] = true;
            queue.push(next);
        }
    }
    return order;
}

The code returns the visitation order, not shortest paths. To reconstruct a path, store parent[next] = current when a vertex is first discovered, then walk those parents backward from the destination. To calculate shortest-edge distances, initialize distance[start] = 0 and assign each newly discovered neighbor distance[current] + 1.

Why mark a vertex when enqueuing?

If you mark only when dequeuing, multiple parents can enqueue the same undiscovered vertex. That wastes queue space and may repeat work. Mark at discovery time to enqueue each vertex once. Validate neighbor identifiers before indexing an array; the examples throw on invalid indices, and assume the caller supplied a consistent graph.

Complexity and limitations

With adjacency lists, BFS is O(V + E) time for all vertices and edges reachable from the start; iterating the whole disconnected graph is O(V + E) across components. The visited array and queue use O(V) auxiliary memory; the returned traversal list also takes O(V) storage. A dense adjacency matrix changes neighbor scanning costs to O(V²) in a full traversal.

BFS does not find minimum total cost when edges have unequal nonnegative weights. Use a weighted shortest-path algorithm, such as Dijkstra, for that problem. A depth-first search does not generally find an unweighted shortest path either.

Try it yourself

Predict the queue after A, then run the explorer. Add an isolated node to a paper sketch: why will one BFS from A never reach it? How would you visit every component?

References: Codecademy BFS, W3Schools graph traversal, Wikipedia BFS.