我们可以拿大学每学期排课的例子来描述这个过程，比如学习大学课程中有：「程序设计」，「算法语言」，「高等数学」，「离散数学」，「编译技术」，「普通物理」，「数据结构」，「数据库系统」等。按照例子中的排课，当我们想要学习「数据结构」的时候，就必须先学会「离散数学」，学习完这门课后就获得了学习「编译技术」的前置条件。当然，「编译技术」还有一个更加前的课程「算法语言」。这些课程就相当于几个顶点 u, 顶点之间的有向边 (u,v) 就相当于学习课程的顺序。教务处安排这些课程，使得在逻辑关系符合的情况下排出课表，就是拓扑排序的过程。
活动（弧）(u,v) 的最迟开始时间：在不推迟整个工期的前提下，活动开始最晚能容忍的时间，记为 l(u,v)，它等于其后继事件的最迟发生时间 - 该事件的持续时间（权值），即 l(u,v)=vl(v)−valvu，其中 valvu 表示 u 到 v 的边的权值（即 u 到 v 的活动的持续时间）。
L ← Empty list that will contain the sorted elementsS ← Set of all nodes with no incoming edgeswhile 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 Sif graph has edges then return error (graph has at least one cycle)else return L (a topologically sorted order)
int n, m;vector<int> G[MAXN];int in[MAXN]; // 存储每个结点的入度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;}
Python
from collections import defaultdict, dequedef 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
using Graph = vector<vector<int>>; // 邻接表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; }};
Python
from enum import Enum, autoclass 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]