3.4Topological sort and strongly connected components
The idea
A topological order of a DAG lists vertices so every edge points forward. Strongly connected components are the maximal mutually reachable groups.
Think of it like this: Getting dressed: socks before shoes; any order that respects the arrows works.
Why it exists
GATE asks which sequences are valid orders or how many there are.
How it works
- Find a vertex with in-degree 0 and output it.
- Delete its outgoing edges, updating in-degrees.
- Repeat; if you get stuck there is a cycle.
- Alternative: reverse DFS finishing order.
Worked example: The sample DAG
A first, then B and C in either order, and so on: there are 14 valid orders. Valid example: A B C D E F G.
Now play with it
- →Run Kahn on the DAG and see in-degrees fall to zero.
- →Think about why a cycle blocks every vertex.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- vertices with in-degree 0 are ready: A
- output A and remove its edges
- output B and remove its edges
- output C and remove its edges
- output D and remove its edges
- output E and remove its edges
- output F and remove its edges
- output G and remove its edges
- every vertex was output: a valid topological order
Only defined for DAGs. Repeatedly output a vertex of in-degree 0. O(V + E). Several orders may be valid.
| Fact | Value |
|---|---|
| Algorithm | Kahn (in-degree 0) or reverse DFS finish order, O(V + E) |
| Exists iff | the directed graph is acyclic |
| Unique iff | consecutive vertices in the order are joined by an edge (a Hamiltonian path exists) |
| SCC algorithm | Kosaraju: DFS, reverse all edges, DFS in decreasing finish time; O(V + E) |
| After contracting SCCs | the graph is a DAG |
Check yourself
A topological ordering exists for a directed graph if and only if
Exam notes (the dense version)
A topological order lists the vertices of a DAG so every edge goes forward. Methods: repeatedly remove in-degree 0 vertices (Kahn), or reverse the DFS finish order. O(V + E). A DAG can have many orders; a unique order exists iff there is a Hamiltonian path. SCCs are found in O(V + E) by Kosaraju (DFS, transpose, DFS) or Tarjan; contracting them yields a DAG.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.