Topological sort or Kahn's algorithm

Hard

Peel off zero-in-degree nodes into an order

Problem

Return a topological ordering of a DAG using Kahn's algorithm (BFS on in-degrees).

In simple words

Repeatedly output a node with no incoming edges, removing it — the sequence respects all arrows.

The idea

Kahn's algorithm builds the order front-to-back. A node can go next only when nothing still points into it (in-degree 0). Queue all such nodes, and each time you output one, delete its outgoing arrows — that may drop a neighbour's in-degree to 0, making it ready. If you place all V nodes there was no cycle; the badges below track each node's remaining in-degree.

The trick

A node is ready only when its in-degree hits 0 — everything it depends on is already placed.
If you can't place all V nodes, the leftovers are trapped in a cycle (so no ordering exists).

←→stepspaceplay

order[ ]

1/8

Optimal

timeO(V+E)spaceO(V)

1compute in-degree of every node2queue all nodes with in-degree 03while queue not empty: u = pop; append u to order4  for each edge u → v: if --indeg[v] == 0: queue v5order has all V nodes  ⇒  valid topological order (no cycle)

Input

nodes: 5, 5 edges

Memory

order: [ ]
queue: —

Output

topo order: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]
Output:: [0, 1, 2, 3]
Explanation:: Every arrow points forward in this order.

Example 2

Input:: n = 2, edges = [[0,1]]
Output:: [0, 1]
Explanation:: 0 comes before 1.

Example 3

Input:: n = 3, edges = [[0,1],[1,2]]
Output:: [0, 1, 2]
Explanation:: A straight chain 0,1,2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.