Topo Sort

Hard

Order nodes so every arrow points forward

Problem

Return a topological ordering of a Directed Acyclic Graph: every edge u→v must place u before v (Kahn's algorithm).

In simple words

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

The idea

A topological order lists the nodes so that every directed edge goes from earlier to later. Kahn's algorithm builds it by repeatedly taking a node with in-degree 0 (nothing left blocking it) and removing its outgoing edges, which may free up more nodes. Placing all V nodes proves the graph is acyclic.

←→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.