Kahn's algorithm
List kahn(List[] graph) {
int[] indeg = new int[graph.length];
for (int u = 0; u < graph.length; u++)
for (int v : graph[u]) indeg[v]++;
Deque q = new ArrayDeque<>();
for (int i = 0; i < graph.length; i++)
if (indeg[i] == 0) q.offer(i);
List order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll(); order.add(u);
for (int v : graph[u]) if (--indeg[v] == 0) q.offer(v);
}
return order;
} Advertisement
DFS-based
DFS, add vertex to output on FINISH. Reverse output. Also O(V+E).
Advertisement
Not unique
Multiple valid topological orders often exist. Kahn's produces lexicographic order if PQ used instead of queue.
Cycle detection
If output length < V → cycle exists (unprocessed vertices).