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