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.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
Start at A.
Mark the source before enqueuing it. This prevents duplicate entries.
queue = [A]Queue · front first
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.#include <queue>
#include <utility>
#include <vector>
std::pair<std::vector<int>, std::vector<int>> bfs(
const std::vector<std::vector<int>>& adj, int source) {
std::vector<int> distance(adj.size(), -1), order;
std::queue<int> queue;
distance[source] = 0;
queue.push(source);
while (!queue.empty()) {
int u = queue.front();
queue.pop();
order.push_back(u);
for (int v : adj[u]) {
if (distance[v] == -1) {
distance[v] = distance[u] + 1;
queue.push(v);
}
}
}
return {distance, order}; // -1 means unreachable.
}