Workspace

Problem workspace

3 day streakD

Breadth-First Search (BFS)

EasyGraphsTraversal

The challenge

Find the minimum number of edges from a source to every reachable vertex in an unweighted graph. Also return the order in which vertices leave the queue.

Use for unweighted graphs or equal positive edge costs. The implementation uses −1 for unreachable vertices; the diagram uses ∞.

Example

From A: distances A:0, B:1, C:2, D:3, E:4, F:1. The first discovery of a vertex is already shortest.

Use the walkthrough below to inspect the input and each state change.

See BFS, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
Connected graphUndirected graph with 6 vertices. Start at A. Mark the source before enqueuing it. This prevents duplicate entries. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
Distance from source
ABCDEF
0∞∞∞∞∞
Step 01 / 13

Start at A.

Mark the source before enqueuing it. This prevents duplicate entries.

queue = [A]

Queue · front first

A
View input edges

A — B · A — F · B — C · C — F · C — D · D — E

Source: A. Adjacency entries follow this edge order.

Put it into code

A FIFO queue processes all vertices at distance d before distance d + 1.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from collections import deque

def bfs(adj, source):
    distance = [-1] * len(adj)
    distance[source] = 0
    queue = deque([source])
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                queue.append(v)  # Mark before enqueuing.

    return distance, order  # -1 means unreachable.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap