Topological Sort

Given a **Directed Acyclic Graph (DAG)** with **n** vertices and a list of directed edges, return a valid **topological ordering** of the vertices.

A topological order ensures that for every directed edge u → v, u appears before v in the ordering.

Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]

Output: [0,1,2,3]

0 must precede 1 and 2; both must precede 3.

Input: n = 3, edges = [[0,1],[1,2]]

Output: [0,1,2]

A simple chain.

Time

O(V + E) using Kahn's algorithm (BFS with in-degree tracking).

Space

O(V) for in-degree array and queue.

#1 — Diamond DAG (any valid order accepted)

Input: n=4 edges=[[0,1],[0,2],[1,3],[2,3]]

Expected: [0,1,2,3]

#2 — Simple chain

Input: n=3 edges=[[0,1],[1,2]]

Expected: [0,1,2]

#3 — No edges — any order valid

Input: n=2 edges=[]

Expected: [0,1]

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.