Topological Sort

Knowledge Summary

Definition of Topological Sorting

Arrange all vertices of a directed acyclic graph (DAG) into a linear order such that for every directed edge (u, v), u appears before v in the order.

Conditions

• Only a DAG has a topological ordering
• If the graph contains a cycle, then a topological ordering does not exist
• A topological ordering is not necessarily unique

Kahn's Algorithm (BFS)

1. Compute the in-degree of every vertex
2. Put all vertices with in-degree 0 into a queue
3. Remove the front vertex from the queue and output it
4. Decrease the in-degree of all its neighbors by 1
5. If a neighbor's in-degree becomes 0, put it into the queue
6. Repeat steps 3-5 until the queue is empty

1vector<int> topoSort(int n, vector<vector<int>>& adj) {
2    vector<int> indegree(n, 0);
3    for (int u = 0; u < n; u++)
4        for (int v : adj[u])
5            indegree[v]++;
6
7    queue<int> q;
8    for (int i = 0; i < n; i++)
9        if (indegree[i] == 0)
10            q.push(i);
11
12    vector<int> result;
13    while (!q.empty()) {
14        int u = q.front(); q.pop();
15        result.push_back(u);
16        for (int v : adj[u])
17            if (--indegree[v] == 0)
18                q.push(v);
19    }
20    return result; // If result.size() < n, then the graph has a cycle
21}

Frequently Tested Points

• Given a DAG, write all possible topological orderings
• Determine whether a given sequence is a valid topological ordering
• Determine whether the graph contains a cycle, that is, whether topological sorting can be completed