图论算法：拓扑排序

什么是拓扑排序？

拓扑排序是对 有向无环图 (Directed Acyclic Graph, DAG) 的顶点进行的一种线性排序。该排序满足这样的条件：对于图中任意一条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 的前面。

简单来说，拓扑排序就是一种能把图“拉直”成一条线性的序列，并保证所有的依赖关系（边的方向）都得到满足的排序方式。一个有向图能进行拓扑排序的 充要条件 是它是一个 DAG。

拓扑排序的结果通常不是唯一的。

应用场景

拓扑排序在现实世界中有很多应用，主要用于解决涉及 依赖关系 的问题，例如：

• 课程安排: 安排课程的先后顺序，必须先修完“数据结构”才能修“算法设计”。
• 任务调度: 在一个项目中，某些任务必须在其他任务开始前完成。
• 软件编译: 编译代码时，需要先编译被依赖的模块。
• 细胞谱系: 在生物学中，确定细胞分化的先后顺序。

算法实现：Kahn 算法 (基��� BFS)

Kahn 算法是实现拓扑排序的常用方法之一，它基于广度优先搜索 (BFS)。

1. 计算入度: 遍历整个图，计算每个顶点的 入度（即有多少条边指向该顶点）。
2. 初始化队列: 找到所有入度为 0 的顶点，将它们放入一个队列中。这些顶点是所有依赖关系的起点，可以作为排序的开头。
3. 循环处理: 当队列不为空时： a. 从队列中取出一个顶点 u。 b. 将 u 加入到拓扑排序的结果序列中。 c. 遍历 u 的所有邻居 v（即所有从 u 出发的边 (u, v)）： i. 将 v 的入度减 1（因为 u 已经被处理，这个依赖关系解除了）。 ii. 如果 v 的入度在减 1 后变为 0，说明 v 的所有前驱依赖都已被满足，此时将 v 加入队列。
4. 检查结果: 循环结束后，检查结果序列中的顶点数量是否等于图中的顶点总数。
   • 如果相等，说明排序成功，该图是一个 DAG。
   • 如果不相等，说明图中存在 环，无法进行拓扑排序。

C++ 伪代码

#include <vector>
#include <queue>

std::vector<int> topologicalSort(int n, const std::vector<std::vector<int>>& adj) {
    std::vector<int> in_degree(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int neighbor : adj[i]) {
            in_degree[neighbor]++;
        }
    }

    std::queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    std::vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (result.size() == n) {
        return result;
    } else {
        return {}; // 表示有环
    }
}

另一种常见的实现方式是基于深度优先搜索 (DFS)，在 DFS 的后序遍历中，逆序输出顶点即可得到拓扑序列。