Kahn's algorithm (BFS)
int[] indeg = new int[n];
for (int u = 0; u < n; u++) for (int v : graph[u]) indeg[v]++;
Queue q = new LinkedList<>();
for (int i = 0; i < n; 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);
}
if (order.size() != n) throw new CycleException(); Advertisement
DFS-based
Deque stack = new ArrayDeque<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) if (!visited[i]) dfs(i, visited, stack);
// Stack popping gives topological order
void dfs(int u, boolean[] visited, Deque stack) {
visited[u] = true;
for (int v : graph[u]) if (!visited[v]) dfs(v, visited, stack);
stack.push(u);
} Advertisement
Cycle detection
Kahn: if not all nodes processed, cycle exists. DFS: track recursion stack; back edge = cycle.
Complexity
Both O(V + E).