Topological Sorting
Topological sorting is an algorithmic technique that finds
an order of the nodes of a directed acyclic graph (DAG)
such that for every directed edge u → v the node u
comes before the node v in the order.
This process is the key in problems where there is an order of dependencies.
Explanation of the infographic
The picture shows the basic concepts of topological sorting in a directed acyclic graph (DAG). The blue circles are the nodes of the graph, and the arrows mark the directions of the edges. The numbers show the order in which the algorithm adds the nodes to the final topological sequence.
The DFS approach: nodes are added to the stack after all their neighbours have been visited. If there is a cycle, the stack will not be able to include all the nodes.
Kahn's algorithm: a node with indegree = 0 is removed and decreases the indegree of its neighbours. If nodes with indegree > 0 are left, the graph contains a cycle and a topological sort does not exist.
The infographic helps you see straight away how both algorithms work and when a graph cannot be sorted.
Approach 1: DFS (the stack method)
The idea:
- We traverse the graph with DFS
- We add a node ONLY after all its neighbours
- At the end we reverse the order
#include <bits/stdc++.h>
using namespace std;
// The adjacency list: g[u] holds all the nodes v such that there is an edge u → v
vector<vector<int>> g;
// state:
// 0 = the node has not been visited
// 1 = the node is currently in the DFS recursion (on the stack)
// 2 = the node has been fully processed
vector<int> state;
vector<int> st; // the result (the topological order, reversed while being built)
// The DFS function returns false if it detects a cycle
bool dfs(int u){
// We mark that we have entered the node u (started processing it)
state[u] = 1;
// We go through all the neighbours
for(int v : g[u]){
// If the neighbour has not been visited yet
if(state[v] == 0){
// We visit it recursively
if(!dfs(v)) return false; // if there is a cycle below → stop
}
// If the neighbour is ALREADY being processed → a cycle!
else if(state[v] == 1){
// This means:
// u → v, but v is already on the DFS path,
// so there is a path v → ... → u
// → we have closed a circle
return false;
}
// If state[v] == 2 → it has already finished → everything is fine
}
// We have finished all the neighbours → now we can add u
state[u] = 2;
// We add it to the result
// (the order will be reversed, which is why we do reverse later)
st.push_back(u);
return true;
}
int main(){
int n, m;
cin >> n >> m;
g.resize(n);
state.assign(n, 0);
// Reading the edges
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b; // a → b
g[a].push_back(b);
}
// We start DFS from every node (because of a disconnected graph)
for(int i = 0; i < n; i++){
if(state[i] == 0){
if(!dfs(i)){
cout << "The graph has a cycle - there is no topological order!";
return 0;
}
}
}
// We reverse because we added the nodes "after processing"
reverse(st.begin(), st.end());
// Printing the result
for(int x : st) cout << x << " ";
}
A concrete example WITHOUT a cycle
n = 4
edges:
0 → 1
0 → 2
1 → 3
2 → 3
The course of DFS:
dfs(0)
→ dfs(1)
→ dfs(3)
→ add 3
→ add 1
→ dfs(2)
→ 3 already finished
→ add 2
→ add 0
st = [3, 1, 2, 0] → after reverse → 0 2 1 3
A concrete example WITH a cycle
n = 3
edges:
0 → 1
1 → 2
2 → 0
The course of DFS:
dfs(0)
→ dfs(1)
→ dfs(2)
→ we try to go to 0
→ state[0] = 1 (still being processed!)
→ A CYCLE DETECTED
The program stops and prints:
The graph has a cycle - there is no topological order!
Why is an ordinary DFS (with visited) NOT enough?
If we use only visited, then:
- we cannot tell whether a node has finished
- or is still being processed
This leads to a mistake:
0 → 1 → 2 → 0
An ordinary DFS says:
"0 has already been visited → ignore it"
But that is wrong, because:
0 has NOT finished yet → it is a cycle!
The essence (the most important things to remember)
✔ We add a node only after all its dependencies
✔ state = 1 means: "we are currently in this node"
✔ If we come across state = 1 again → a cycle
✔ If there is a cycle → a topological order does NOT exist
✔ reverse is needed because we add a node AFTER processing it
Approach 2: Kahn's algorithm (BFS)
This approach detects a cycle naturally and is often more intuitive for beginners.
The basic idea: we always choose a node that has no dependency (in-degree = 0).
The task
N nodes and M directed edges are given.
Every edge a → b means that the node a must be processed before the node b.
Determine one order of all the nodes such that all the conditions are met.
If such an order does not exist (because of a cycle), print:
The graph has a cycle!
Input:
- The first line:
n m - The next
mlines: pairsa b
Output:
- Print one valid order of the nodes
- Or a message that there is a cycle
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
// The adjacency list: g[u] = all v such that there is u → v
vector<vector<int>> g(n);
// indeg[v] = the number of edges coming into the node v
vector<int> indeg(n, 0);
// Reading the graph
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b; // a → b
g[a].push_back(b);
// we increase the number of incoming edges of the node b
indeg[b]++;
}
queue<int> q;
// We put all the nodes that have no dependencies into the queue
for(int i = 0; i < n; i++){
if(indeg[i] == 0){
q.push(i);
}
}
vector<int> order; // the final topological order
// The main loop (BFS style)
while(!q.empty()){
// We take a node that has no dependencies
int u = q.front();
q.pop();
// We add it to the result
order.push_back(u);
// We "remove" the node u from the graph,
// i.e. we decrease the indegree of its neighbours
for(int v : g[u]){
indeg[v]--;
// If a neighbour has no more incoming edges,
// it means that all its dependencies are solved
if(indeg[v] == 0){
q.push(v);
}
}
}
// If we have not processed all the nodes → there is a cycle
if((int)order.size() != n){
cout << "The graph has a cycle!";
return 0;
}
// Printing the topological order
for(int x : order) cout << x << " ";
}
A concrete example (without a cycle)
n = 6
edges:
0 → 2
1 → 2
1 → 3
2 → 4
3 → 4
4 → 5
A visual display of the graph:
0 1
\ / \
\ / \
v v v
2 3
\ /
v v
4
|
v
5
The initial in-degrees:
0: 0
1: 0
2: 2
3: 1
4: 2
5: 1
The initial queue:
q = [0, 1]
The steps of the algorithm:
we take out 0 → order = [0]
indeg[2] = 1
we take out 1 → order = [0, 1]
indeg[2] = 0 → we put it in
indeg[3] = 0 → we put it in
q = [2, 3]
we take out 2 → order = [0, 1, 2]
indeg[4] = 1
we take out 3 → order = [0, 1, 2, 3]
indeg[4] = 0 → we put it in
we take out 4 → order = [0, 1, 2, 3, 4]
indeg[5] = 0 → we put it in
we take out 5 → order = [0, 1, 2, 3, 4, 5]
One valid topological order:
0 1 2 3 4 5
An example with a cycle
n = 3
edges:
0 → 1
1 → 2
2 → 0
A visual display of the cyclic graph:
0 → 1
↑ |
| v
2 ←--
in-degree:
0: 1
1: 1
2: 1
The initial queue:
q = []
No node has indegree = 0 → the algorithm cannot start.
order = []
Since:
order.size() != n
we conclude: the graph has a cycle and there is no valid topological order.
The essence of Kahn's algorithm
✔ We always choose a node without dependencies (indegree = 0)
✔ With every step we "remove" a node from the graph
✔ If some nodes are left at the end → they are in a cycle
✔ If at the start there is no node with indegree = 0 → there is certainly a cycle
Intuition (the most important part)
Imagine tasks:
- some tasks have no prerequisites → we do them first
- when we finish them → new tasks are unlocked
If at some moment:
there is no task without prerequisites
→ it means that the tasks are waiting for one another → a cycle
Explanation of the basic idea
The sentence: "we always choose a node that has no dependency (in-degree = 0)" means the following:
If no edge comes into some node v,
it means that:
- nothing has to be done before it
- it has no prerequisites
- we can process it straight away
That is why we put such nodes into the queue and process them first.
When we process some node u, we practically "remove" it from the graph:
- we decrease the number of incoming edges of its neighbours
- and in this way we may unlock new nodes
For example, we have a module whose prerequisites are shown by the input:
0 → 2
1 → 2
A visual display of the graph with arrows:
0 1
\ /
\ /
2
Node 2 has two prerequisites (0 and 1), so it cannot go straight away. But 0 and 1 have no prerequisites → they can be processed straight away.
Steps:
1) We process 0 and 1
2) Now 2 has no more incoming edges → it can be processed
If at some moment:
there is no node with indegree = 0
it means that:
all the remaining nodes depend on one another → there is a cycle
A real task (where this is used)
You are working on a system for compiling a software project.
The project consists of N modules.
Some modules depend on others — for module B to be compiled,
module A must be compiled first.
All the dependency relations are given in the form of pairs A B.
Task:
Determine the order of compiling all the modules so that all the dependencies are respected.
If that is not possible (because of a circular dependency), print:
ERROR: circular dependency
Example:
Input:
5 4
0 2
1 2
2 3
3 4
A visual display of the graph:
0 1
\ /
\ /
2
|
3
|
4
Explanation:
- 0 and 1 have no dependencies → they can go first
- after them → 2
- then 3
- then 4
One valid output:
0 1 2 3 4
An example with an error:
3 3
0 1
1 2
2 0
A visual display of the cycle:
0 → 1 → 2
↑ |
|_________|
Here there is a circular dependency → no module can go first, there is no solution.
The essence (in one sentence)
We do only what currently has no prerequisites — and in this way we gradually unlock the rest.
A visual explanation of topological sorting
Topological sorting determines the order of executing the nodes of a directed acyclic graph (DAG).
For every edge u → v the node u must be
before the node v in the final order.
An example graph:
0
/ \
v v
1 2
\ /
v
3
|
v
4
The meaning of the edges:
- 0 must be before 1
- 0 must be before 2
- 1 must be before 3
- 2 must be before 3
- 3 must be before 4
One possible topological order is:
0 → 1 → 2 → 3 → 4
But there is another valid order too:
0 → 2 → 1 → 3 → 4
It is important to understand that topological sorting often has several valid solutions.
Kahn's algorithm – step by step
Kahn's algorithm uses the array indegree,
which says how many incoming edges every node has.
- Nodes with
indegree = 0have no dependencies - Such nodes can be executed straight away
For the previous graph the indegree values are:
Node: 0 1 2 3 4 indegree: 0 1 1 2 1
The algorithm starts from the nodes that have indegree = 0.
A table of how Kahn's algorithm runs (with explanations)
| Step | Node taken out | State of the queue | Indegree array | Explanation |
|---|---|---|---|---|
| Start | - | [0] | [0,1,1,2,1] | The start of the algorithm; we choose the nodes with indegree = 0 (0 has no prerequisites) |
| 1 | 0 | [1,2] | [0,0,0,2,1] | We removed 0; the indegree of nodes 1 and 2 dropped from 1 to 0 → both are now ready |
| 2 | 1 | [2] | [0,0,0,1,1] | We removed 1; the indegree of node 3 dropped from 2 to 1 → node 3 is not ready yet |
| 3 | 2 | [3] | [0,0,0,0,1] | We removed 2; the indegree of node 3 dropped from 1 to 0 → node 3 is now ready |
| 4 | 3 | [4] | [0,0,0,0,0] | We removed 3; the indegree of node 4 dropped from 1 to 0 → node 4 is now ready |
| 5 | 4 | [] | [0,0,0,0,0] | We removed 4; the queue is empty → all the nodes have been processed, the topological order is found |
The order in which the nodes are removed from the queue gives the topological order of the graph:
In this example we get:
0 → 1 → 2 → 3 → 4
The complexity of the algorithm
Let:
- V – the number of nodes
- E – the number of edges
The complexity of both approaches is the same:
- DFS topological sorting: O(V + E)
- Kahn's algorithm: O(V + E)
This means that every node and every edge is processed at most once.
An example of practical use
One of the most common uses of topological sorting is planning tasks that depend on one another.
An example: subjects at a university.
Mathematics → Algorithms Programming → Algorithms Algorithms → Artificial intelligence
Topological sorting gives the order in which the exams can be taken:
Mathematics → Programming → Algorithms → Artificial intelligence
If there were a dependency that makes a cycle, for example:
Algorithms → Mathematics
then topological sorting would not be possible, because every subject would need another one as a prerequisite.
Practice tasks — topological sorting
1. Topological sorting with DFS
Task text
A directed acyclic graph (DAG) is given. Find a topological order of the nodes using the DFS algorithm.
Example
Graph:
0 → 1
0 → 2
1 → 3
2 → 3
3 → 4
A possible output:
0 2 1 3 4
2. Topological sorting — Kahn's algorithm
Task text
A directed graph is given. Find a topological order using Kahn's algorithm (the BFS approach).
Example
Graph:
0 → 1
0 → 2
1 → 3
2 → 3
A possible output:
0 1 2 3
3. Detecting a cycle with topological sorting
Task text
A directed graph is given. Check whether the graph contains a cycle.
If the graph has a cycle, topological sorting is not possible.
4. Planning a project (topological sorting)
Task text
A big project consists of N tasks.
Some tasks must be finished before others can start.
These dependencies are represented as a directed graph.
Find an order of executing the tasks so that all the dependencies are respected.
Example
Input:
6 6
1 3
2 3
3 4
3 5
4 6
5 6
Output:
1 2 3 4 5 6
5. Detecting a cycle in a system of dependencies
Task text
In a system of software modules some modules depend on others. If there is a cycle of dependencies, the system cannot be compiled.
Check whether the dependency graph contains a cycle.
Example
Input:
3 3
1 2
2 3
3 1
Output:
CYCLE
6. The earliest time to finish a project
Task text
A project consists of N tasks.
Every task has a duration.
Some tasks can start only after others have finished.
Compute the minimum time to finish the whole project.
Example
Tasks:
1 (3 days)
2 (2 days)
3 (4 days)
Dependencies:
1 → 3
2 → 3
Output:
7
Task 3 can start only when tasks 1 and 2 have finished. The earliest starting time is max(3,2) = 3. The total time = 3 + 4 = 7.
The program reads N M, then the N durations, and then the M dependencies a b (for the example: 3 2 / 3 2 4 / 1 3 / 2 3).
Advanced tasks (competition level) — BFS and DFS
7. The farthest node in a network (BFS)
Task text
A network of computers is given as an unweighted graph.
Find the node that is the farthest
from the starting computer S.
The distance between two computers is the number of cables (edges) that have to be travelled.
If there are several such nodes, print any of them.
Example
Input:
6 6
1 2
1 3
2 4
3 5
5 6
4 6
S = 1
Output:
6
The program reads S as the last number of the input (for the example: 1).
8. The number of connected components (DFS)
Task text
A network of islands connected by bridges is given. Every island is a node in the graph, and a bridge is an edge.
Determine how many separate groups of islands there are, that is, how many connected components the graph has.
Example
Input:
7 4
1 2
2 3
4 5
6 7
Output:
3
9. Detecting a cycle in an undirected graph (DFS)
Task text
Check whether an undirected graph contains a cycle.
A cycle exists if during the DFS traversal we come across an already visited node that is not the parent of the current node.
Example
Input:
4 4
1 2
2 3
3 4
4 2
Output:
YES
Olympiad level — advanced graph algorithms
10. The longest path in a DAG
Task text
A directed acyclic graph (DAG) is given.
Find the length of the longest path from the node S
to all the other nodes.
Since the graph has no cycles, the problem can be solved with topological sorting and dynamic programming.
Example
Input:
6 6
1 2
1 3
2 4
3 4
4 5
5 6
S = 1
Output (dp[1] … dp[6]):
0 1 1 2 3 4
The program reads S as the last number of the input; the value -1 means that a node cannot be reached from S.
11. Bridges in a graph
Task text
In a road network some roads are critical. If such a road is removed, the graph becomes disconnected.
Such edges are called bridges. Find all the bridges in the graph.
Example
Input:
5 5
1 2
2 3
3 4
2 4
4 5
Output:
Bridge: 4 - 5
Bridge: 1 - 2
12. Articulation points
Task text
In a communication network some points are critical. If such a point is removed, the network falls apart into several components.
Such nodes are called articulation points.
Example
Input:
5 5
1 2
2 3
3 4
2 4
4 5
Output:
2 4
Check your knowledge
Open the quiz
Topological sorting
1. For which graphs does a topological order exist?
2. Which nodes are put into the queue first in Kahn's algorithm?
3. What does it mean if Kahn's algorithm does not place all the nodes?
