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).