Lesson 7 of 17 · Graphs and trees

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.



Topological sorting of DAGs in C++: the DFS and Kahn algorithms with the order of the nodes and cycle detection
Figure 1: A visual display of topological sorting in a DAG with the DFS and Kahn algorithms. See how the nodes are sorted in order and how a cycle is detected.

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:

  1. We traverse the graph with DFS
  2. We add a node ONLY after all its neighbours
  3. 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 m lines: pairs a 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 = 0 have 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?