图
拓扑排序
拓扑排序接收一个有向无环图（DAG），把它的顶点排成一行，使每条边都指向前方——若有一条从 A 到 B 的边，那么在排序中 A 就排在 B 前面。它在日常中的含义就是依赖解析：“先做这个，再做那个”。穿袜子必须在穿鞋之前；大学课程有先修要求；构建系统必须先编译库，再编译用到它的程序。
它只对 DAG 有效：图必须是有向的（箭头说明谁必须先于谁）且无环的（没有环）。环意味着 A 必须排在 B 前、B 又必须排在 A 前——这是一个不可能成立的矛盾要求，因此根本不存在合法的排序。正确的拓扑序通常不止一种，因为彼此之间没有依赖关系的项目，相对位置可以互换。
两种标准方法的时间都是 O(V + E)。Kahn 算法反复取出任何一个“已无入边”（即没有未满足的依赖）的顶点并输出它。DFS 方法跑一次深度优先搜索，在每个顶点的递归结束时输出它，最后把列表反转。两种方法都能给出合法的执行顺序——而如果根本排不出顺序，这本身就证明了图中含有环。
queue<int> q;
for (int v = 0; v < n; ++v)
if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int nb : adj[v])
if (--indeg[nb] == 0) q.push(nb);
}每移除一个顶点，就把它后继的入度减一，从而“释放”它们。
拓扑排序只对 DAG 有定义。排不出完整顺序，正是检测有向图中环的标准办法。
又称
另见