拓扑排序-未完纪

给定一个有 n 个顶点、m 条边的有向图，需要找出顶点的一种顺序，使每条边都从序号较小的顶点指向序号较大的顶点。

换句话说，要寻找一个顶点排列，即拓扑序，使其符合图中所有边定义的先后关系。

下图展示一个有向图及其一种拓扑序：

拓扑序不一定唯一。例如，有 a、b、c 三个顶点，从 a 可以到达 b 和 c，但 b 与 c 之间两个方向都没有路径，就可能存在多种排列。示例图也有多个拓扑序，下面是另一种：

拓扑序也可能根本不存在。有向图只有在不含环时才存在拓扑序。如果环中包含 a 和 b，那么因为 a 能到达 b，a 的序号应小于 b；又因为 b 能到达 a，a 的序号又应大于 b，产生矛盾。本文算法也通过构造说明，每个有向无环图都至少存在一个拓扑序。

一个常见应用是：有 n 个值未知的变量，已知部分变量之间的大小关系。需要检查这些约束是否矛盾；若不矛盾，按升序输出变量，多个答案时任选一个。这正是在有 n 个顶点的图上寻找拓扑序的问题。

算法

我们使用深度优先搜索解决这一问题。（depth-first search）

假设图没有环，深度优先搜索会做什么？

从顶点 v 开始时，DFS 尝试沿 v 的所有出边遍历。遇到终点已访问的边就停止；其余边则继续遍历，在终点递归执行。

因此，当 dfs(v) 调用结束时，从 v 可达的所有顶点，无论直接还是间接可达，都已被搜索访问。

在 dfs(v) 结束时把 v 添加到列表。所有可达顶点已经访问，因此会在 v 之前加入列表。通过一轮或多轮 DFS 对全部顶点执行这一操作。对于每条边 v → u，因为 u 从 v 可达，u 在列表中一定先于 v。将列表中的顶点依次标记为 n−1、n−2、…、1、0，就得到拓扑序。也就是说，列表本身表示逆拓扑序。

也可以用 DFS 的退出时间解释。顶点 v 的退出时间是 dfs(v) 调用结束的时间，可从0到 n−1编号。v 的退出时间总大于任一从它可达顶点的退出时间，因为这些顶点要么在 dfs(v) 之前访问，要么在调用期间访问。因此按退出时间递减排列顶点，就是所需拓扑序。

实现

以下实现假定图无环，即拓扑序存在。如有必要，可以按深度优先搜索文章中的方法检查有向环。（depth-first search）

int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

主函数 topological_sort 初始化 DFS 变量、启动搜索，并把答案存入 ans。即使图有环，结果仍具有一种有用性质：若从 v 可达 u，而从 u 不可达 v，那么 v 总在结果数组中先于 u。Kosaraju 算法利用这一性质，提取有环图的强连通分量并对分量进行拓扑排序。（Kosaraju's algorithm）