The challenge
Order the vertices of a directed graph so every prerequisite u appears before its dependent v for each edge u → v. Report failure if a directed cycle prevents a complete ordering.
A full topological ordering exists exactly when the directed graph is acyclic (a DAG).
Example
A → B → F → C → D → E is valid. Adding D → B creates a cycle; Kahn outputs only the unblocked prefix.
Use the walkthrough below to inspect the input and each state change.
See Kahn, step by step
Follow the edges. Watch the state change.
Directed · 6 vertices · 6 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisited
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 1 | 1 |
Step 01 / 14
Find vertices with no prerequisites.
Count incoming edges. Only vertices with indegree zero may enter the initial queue.
queue = all vertices with indegree 0Zero-indegree queue · front first
A
View input edges
A → B · A → F · B → C · F → C · C → D · D → E
Put it into code
A zero-indegree vertex is ready because none of its remaining prerequisites block it.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
from collections import deque
def topological_sort(adj):
indegree = [0] * len(adj)
for neighbors in adj:
for v in neighbors:
indegree[v] += 1
queue = deque(u for u, d in enumerate(indegree) if d == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == len(adj) else None#include <optional>
#include <queue>
#include <vector>
std::optional<std::vector<int>> topological_sort(
const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size());
std::vector<int> indegree(n, 0), order;
for (const auto& neighbors : adj)
for (int v : neighbors) ++indegree[v];
std::queue<int> queue;
for (int u = 0; u < n; ++u)
if (indegree[u] == 0) queue.push(u);
while (!queue.empty()) {
int u = queue.front();
queue.pop();
order.push_back(u);
for (int v : adj[u])
if (--indegree[v] == 0) queue.push(v);
}
if (static_cast<int>(order.size()) != n) return std::nullopt;
return order;
}