Skip to content

Topological Sorting

Definition

Topological sorting addresses the problem of ordering all nodes in a Directed Acyclic Graph (DAG).

We can illustrate this process with the example of university course scheduling. Consider university courses such as "Programming", "Algorithm Language", "Advanced Mathematics", "Discrete Mathematics", "Compiler Technology", "General Physics", "Data Structures", "Database Systems", etc. Following the example schedule, to study "Data Structures", one must first learn "Discrete Mathematics". After completing this course, one obtains the prerequisite for "Compiler Technology". Of course, "Compiler Technology" also has an earlier prerequisite course, "Algorithm Language". These courses correspond to vertices \(u\), and the directed edges \((u,v)\) between vertices represent the order in which courses must be taken. The academic office arranges these courses to produce a timetable that respects the logical dependencies, which is the process of topological sorting.

topo

However, if one day the scheduling teacher dozes off and says that to study Data Structures, one must first study Operating Systems, and the prerequisite for Operating Systems is Data Structures, then which one should be studied first (assuming they cannot be taken simultaneously)? Here, a cycle appears between Data Structures and Operating Systems. Clearly, students cannot determine which course to take first, making topological sorting impossible. If a directed graph contains a cycle, topological sorting cannot be performed.

Thus, we can say that in a DAG (Directed Acyclic Graph), we arrange the vertices in a linear order such that for any directed edge \((u,v)\) from vertex \(u\) to vertex \(v\), \(u\) appears before \(v\).

Also, given a DAG, if there is an edge from \(i\) to \(j\), then \(j\) is said to depend on \(i\). If there is a path from \(i\) to \(j\) (\(i\) is reachable to \(j\)), then \(j\) is said to indirectly depend on \(i\).

The goal of topological sorting is to order all nodes so that nodes appearing earlier do not depend on nodes appearing later.

AOV Network

In daily life, a large project can be seen as a collection of several subprojects, which must have a certain order of execution—some subprojects can only start after others are completed.

We use a directed graph to represent the precedence relationships among subprojects, where the precedence relationships are directed edges. This type of directed graph is called an Activity On Vertex Network (AOV Network). An AOV network must be a directed acyclic graph, i.e., without cycles. Unlike a DAG, activities in an AOV network are represented on vertices. (The example graph above is an AOV network.)

In an AOV network, vertices represent activities, and arcs represent precedence relationships between activities. An AOV network should not contain cycles, allowing us to find a vertex sequence where the predecessor activities of each vertex appear before the vertex itself. Such a sequence is called a topological sequence (an AOV network may have multiple topological sequences). The process of constructing a topological sequence from an AOV network is called topological sorting. Therefore, topological sorting can also be interpreted as arranging all activities in an AOV network into a sequence such that the predecessor activities of each activity appear before it (an AOV network may have multiple topological sorts).

  • Predecessor Activity: The activity at the starting point of a directed edge is called the predecessor activity of the endpoint (an activity can only proceed after all its predecessors are completed).

  • Successor Activity: The activity at the endpoint of a directed edge is called the successor activity of the starting point.

To detect whether an AOV network contains a cycle, construct a topological sequence and check if it includes all vertices.

Steps to Construct a Topological Sequence

  1. Select a vertex with in-degree zero from the graph.
  2. Output this vertex, and remove it and all its outgoing edges from the graph.

Repeat the above two steps until all vertices are output (topological sorting is complete), or until no vertex with in-degree zero exists, indicating the graph contains a cycle, topological sorting cannot be completed, and a deadlock occurs.

Critical Path and AOE Network

Corresponding to the AOV network is the Activity On Edge Network (AOE Network), where edges represent activities. An AOE network is a weighted directed acyclic graph where vertices represent events, and arcs represent the duration of activities. Typically, an AOE network can be used to estimate the completion time of a project. An AOE network should be acyclic, with a unique source vertex (with zero in-degree) and a unique sink vertex (with zero out-degree).

topo

Some activities in an AOE network can be performed in parallel, so the shortest time to complete the entire project is the length of the longest activity path from the start point to the finish point (here, path length refers to the sum of the durations of activities along the path, i.e., the sum of arc weights, not the number of arcs). Since a project requires completing all activities within it, the longest activity path is also the critical path, determining the total project completion time.

  • Activity: In an AOE network, arcs represent activities. The weight of an arc indicates the duration of the activity. An activity starts after its predecessor event (the starting vertex of the arc) is triggered.

  • Event: In an AOE network, vertices represent events. An event is triggered when all its predecessor activities (arcs pointing to the vertex) are completed.

  • Earliest Occurrence Time of Event (Vertex) \(v_i\): The earliest possible occurrence time of the event, denoted \(ve(i)\). It determines the earliest start time of activities beginning at this vertex. Clearly, the earliest occurrence time of the source vertex is 0. Since an event requires all its predecessor activities to be completed, it equals the maximum path length from the source to the vertex. The recurrence is: \(ve(i) = \max\{ve(j) + val^j_i ~\vert~ j \in pre_i\}\), where \(val^j_i\) is the weight of the edge from \(j\) to \(i\) (i.e., the duration of the activity from \(j\) to \(i\)), and \(pre_i\) is the set of all predecessor events of \(i\).

  • Latest Occurrence Time of Event (Vertex) \(v_i\): The latest tolerable occurrence time of the event without delaying the entire project, denoted \(vl(i)\). It determines the latest start time of all activities ending at this state. It equals the minimum of the latest start times of all successor activities, i.e., \(vl(i) = \min\{vl(j) - val^i_j ~\vert~ j \in nxt_i\}\), where \(val^i_j\) is the weight of the edge from \(i\) to \(j\) (i.e., the duration of the activity from \(i\) to \(j\)), and \(nxt_i\) is the set of all successor events of \(i\).

  • Earliest Start Time of Activity (Arc) \((u, v)\): The earliest possible start time of the activity, denoted \(e(u,v)\). Clearly, it equals the earliest occurrence time of its predecessor event, i.e., \(e(u,v)=ve(u)\).

  • Latest Start Time of Activity (Arc) \((u, v)\): The latest tolerable start time of the activity without delaying the entire project, denoted \(l(u,v)\). It equals the latest occurrence time of its successor event minus the duration (weight) of the activity, i.e., \(l(u,v)=vl(v)-val^u_v\), where \(val^u_v\) is the weight of the edge from \(u\) to \(v\) (i.e., the duration of the activity from \(u\) to \(v\)).

  • Critical Path: The longest path from the source to the sink in an AOE network.

  • Critical Activity: An activity on the critical path, where its earliest start time equals its latest start time.

Recurrence for Earliest and Latest Occurrence Times

Compute in topological order: earliest occurrence times are computed forward, and latest occurrence times are computed backward. The recurrence formulas are as shown in Basic Concepts Related to AOE Networks above.

Kahn's Algorithm

Process

Initially, set \(S\) contains all vertices with in-degree \(0\), and \(L\) is an empty list.

Each time, take a vertex \(u\) from \(S\) (any vertex) and append it to \(L\). Then remove all edges \((u, v_1), (u, v_2), (u, v_3) \cdots\) from \(u\). For each edge \((u, v)\), if removing it reduces the in-degree of \(v\) to \(0\), add \(v\) to \(S\).

Repeat this process until \(S\) is empty. Check if any edges remain in the graph. If so, the graph contains at least one cycle; otherwise, return \(L\), where the order of vertices in \(L\) is the topological order.

First, see the pseudocode from Wikipedia.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

The core of the code is to maintain a set of vertices with in-degree \(0\).

Refer to the following diagram.

topo

The sorting result is: 2 -> 8 -> 0 -> 3 -> 7 -> 1 -> 5 -> 6 -> 9 -> 4 -> 11 -> 10 -> 12

Time Complexity

Assume the graph \(G = (V, E)\). Initializing the set \(S\) of vertices with in-degree \(0\) requires traversing the entire graph and checking every edge, resulting in \(O(E+V)\) complexity. Then operating on this set also requires \(O(E+V)\) time complexity.

Thus, the total time complexity is \(O(E+V)\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n, m;
vector<int> G[MAXN];
int in[MAXN];  // Stores the in-degree of each vertex

bool toposort() {
  vector<int> L;
  queue<int> S;
  for (int i = 1; i <= n; i++)
    if (in[i] == 0) S.push(i);
  while (!S.empty()) {
    int u = S.front();
    S.pop();
    L.push_back(u);
    for (auto v : G[u]) {
      if (--in[v] == 0) {
        S.push(v);
      }
    }
  }
  if (L.size() == n) {
    for (auto i : L) cout << i << ' ';
    return true;
  }
  return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict, deque


def topo_sort(graph):
    lst = []
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    s = deque([u for u in graph if in_degree[u] == 0])
    while s:
        u = s.popleft()
        lst.append(u)
        for v in graph.get(u, []):
            in_degree[v] -= 1
            if in_degree[v] == 0:
                s.append(v)

    return None if any(in_degree.values()) else lst

DFS Algorithm

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using Graph = vector<vector<int>>;  // Adjacency list

struct TopoSort {
  enum class Status : uint8_t { to_visit, visiting, visited };

  const Graph& graph;
  const int n;
  vector<Status> status;
  vector<int> order;
  vector<int>::reverse_iterator it;

  TopoSort(const Graph& graph)
      : graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

  bool sort() {
    for (int i = 0; i < n; ++i) {
      if (status[i] == Status::to_visit && !dfs(i)) return false;
    }
    return true;
  }

  bool dfs(const int u) {
    status[u] = Status::visiting;
    for (const int v : graph[u]) {
      if (status[v] == Status::visiting) return false;
      if (status[v] == Status::to_visit && !dfs(v)) return false;
    }
    status[u] = Status::visited;
    *it++ = u;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from enum import Enum, auto


class Status(Enum):
    to_visit = auto()
    visiting = auto()
    visited = auto()


def topo_sort(graph: list[list[int]]) -> list[int] | None:
    n = len(graph)
    status = [Status.to_visit] * n
    order = []

    def dfs(u: int) -> bool:
        status[u] = Status.visiting
        for v in graph[u]:
            if status[v] == Status.visiting:
                return False
            if status[v] == Status.to_visit and not dfs(v):
                return False
        status[u] = Status.visited
        order.append(u)
        return True

    for i in range(n):
        if status[i] == Status.to_visit and not dfs(i):
            return None

    return order[::-1]

Time Complexity: \(O(E+V)\)
Space Complexity: \(O(V)\)

Proof of Correctness

Consider a graph. After removing a vertex with in-degree \(0\), if the new graph can be topologically sorted, then the original graph certainly can. Conversely, if the original graph can be topologically sorted, then the graph after removal can also be sorted.

Applications

Topological sorting can determine whether a graph contains a cycle and whether the graph is a linear chain. It can also be used to find the critical path in an AOE network and estimate the shortest project completion time.

Finding Lexicographically Largest/Smallest Topological Order

Replace the queue in Kahn's algorithm with a max-heap/min-heap priority queue. The total time complexity becomes \(O(E+V \log{V})\).

Exercises

CF 1385E: Requires construction via topological sorting.

Luogu P1347: Topological sorting template.

References

  1. Discrete Mathematics and Its Applications. ISBN:9787111555391
  2. Topological sorting - Wikipedia
  3. Data Structures Lecture 9 (Graphs: Topological Sorting, Critical Path, Shortest Path) - Zhihu Column
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用