拓扑排序：给任务排个队，不打架！

你有没有过这样的烦恼：早上想穿鞋，结果发现袜子还没穿？又或者，你想先吃早饭再刷牙，却被妈妈喊回去重来？生活中很多事情都有严格的先后顺序。比如做一道菜，你要先洗菜、切菜，再下锅炒，不能反过来。如果有一大堆任务，它们之间有很多这样的“先做A，再做B”的关系，我们怎么找出一个合理的顺序，让所有任务都能在它的前提任务完成后才开始呢？这就是拓扑排序要解决的问题。

拓扑排序是图论里一种非常实用的算法。它把每个任务看作一个点（顶点），如果任务A必须在任务B之前完成，我们就画一条从A指向B的箭头（有向边）。这样所有任务和它们之间的先后关系就构成了一张有向图。注意，这张图里绝对不能有环——比如“你先穿鞋再穿袜子”和“你先穿袜子再穿鞋”同时出现，就会矛盾，谁也没法先开始。这种没有环的有向图叫做有向无环图（DAG），只有DAG才能进行拓扑排序。

拓扑排序的结果不唯一，只要满足所有先后关系，任何一个顺序都可以。比如起床穿衣服，你可以先穿袜子再穿鞋，也可以先穿裤子再穿袜子，都是合理的。

核心思想：从“没任何前置任务”的开始

想象你在做一张任务清单，每个任务都标着它需要先完成哪些其他任务。你该怎么做？很简单：先找那些没有任何前置任务的任务（比如“穿袜子”没有前置，而“穿鞋”的前置是“穿袜子”），把它们先做了。然后，一旦你完成了某个任务，它就会“解放”那些依赖它的任务——比如“穿袜子”完成后，“穿鞋”的前置任务就少了一个。不断重复，直到所有任务都被做完了。如果最后还有任务一直没被做，说明它们之间有循环依赖，没法完成。

这个找任务先后顺序的过程，就是Kahn算法（卡恩算法）。它用了一个叫“入度”的概念。入度是指向一个顶点的边的数量，简单说就是“这个任务有多少个前置任务”。一开始入度为0的任务就是那些没有前置的，可以立刻做。

具体步骤：

统计每个任务的入度（前置数量）。
把所有入度为0的任务放进一个队列（或者栈）里。
从队列中取出一个任务，把它加入最终顺序。
对于这个任务指向的所有后续任务，把它们的入度减1（相当于这个前置任务完成了）。
如果减完后某个后续任务的入度变成0，就把它也加入队列。
重复步骤3~5，直到队列为空。
最后检查顺序里的任务数量是否等于总任务数。相等说明成功，否则说明存在环。

代码一步步拆解

下面我们用一个具体的例子来写代码。假设有6个任务（编号0到5），它们的先后关系如下：

任务0必须在任务2之前（0 → 2）
任务1必须在任务2和任务3之前（1 → 2，1 → 3）
任务2必须在任务4之前（2 → 4）
任务3必须在任务5之前（3 → 5）
任务4必须在任务5之前（4 → 5）

我们可以画成一张图：0和1是起点，2和3依赖它们，4和5在最后。这完全是一个有向无环图。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n = 6;                  // 任务数量，6个任务编号0~5
    vector<int> adj[6];         // 邻接表，adj[u]存储u指向的所有任务
    int indeg[6] = {0};         // 入度数组，indeg[v]表示任务v有多少前置任务

    // 添加边（先后关系）：任务u必须在任务v之前
    adj[0].push_back(2);        // 0→2，所以2的入度+1
    indeg[2]++;                 // 任务2增加一个前置任务0
    adj[1].push_back(2);        // 1→2，任务2又多一个前置
    indeg[2]++;                 // 现在任务2的入度变成2（需要0和1都完成）
    adj[1].push_back(3);        // 1→3
    indeg[3]++;                 // 任务3入度变成1
    adj[2].push_back(4);        // 2→4
    indeg[4]++;                 // 任务4入度变成1
    adj[3].push_back(5);        // 3→5
    indeg[5]++;                 // 任务5入度变成1
    adj[4].push_back(5);        // 4→5
    indeg[5]++;                 // 任务5入度变成2（需要3和4都完成）

    queue<int> q;               // 队列，用于存放当前入度为0的任务
    // 遍历所有任务，把一开始就没有前置的（入度为0）加入队列
    for (int i = 0; i < n; ++i) {
        if (indeg[i] == 0) {
            q.push(i);          // 任务i可以立即开始
        }
    }

    vector<int> order;          // 存储最终的拓扑排序结果
    while (!q.empty()) {
        int u = q.front();      // 取出一个可以做的任务
        q.pop();
        order.push_back(u);     // 把它加入顺序列表

        // 遍历这个任务指向的所有后续任务
        for (int v : adj[u]) {
            indeg[v]--;          // 因为u完成了，v的前置任务少了一个
            if (indeg[v] == 0) { // 如果v的前置全完成了，v也可以做了
                q.push(v);
            }
        }
    }

    // 检查是否所有任务都被安排进去了
    if (order.size() != n) {
        cout << "存在环，无法拓扑排序" << endl;
    } else {
        cout << "一个合理的顺序: ";
        for (int x : order) {
            cout << x << " ";   // 输出任务编号
        }
        cout << endl;
    }
    return 0;
}

运行结果会输出类似 0 1 2 3 4 5 或者 1 0 2 3 4 5 这样的顺序。由于0和1没有依赖关系，谁先都可以。

新手容易犯的错误

忘记初始化入度数组：代码中 int indeg[6] = {0}; 把全部初始化为0，必须保证一开始每个任务的入度都是0，然后每加一条边累加。有些同学只给部分初始化，导致结果错误。
入度更新只做一次：在循环中，indeg[v]-- 必须放在 for 循环里，每处理一个前置任务就要减1。不能只减一次就认为所有前置都完成了。
没有检查环：如果最终的顺序大小不等于任务总数，说明图中有环。有些同学忘了这一步，以为只要队列空就结束了，但可能还有没加入队列的任务。
用错容器：代码里用 queue 保证顺序是先进先出，但其实用 stack 或 vector 也可以，只是输出的顺序可能不同。但要注意不能用 set 随意取出，因为入度为0的任务可能有多个，我们需要把它们都存起来。
图中存在自环或平行边：如果某个任务指向自己（0→0），那就是自环，入度永远减不完，肯定无法拓扑排序。另外如果两条重复的边，入度会重复加，导致实际需要的前置任务数量比真实的多，排序会错误。

完整示例：计算课程顺序

假设你是一个初中生，要选6门选修课，有些课必须先修其他课才能上。课程编号和前置关系如下：

0：基础数学（无前置）
1：基础英语（无前置）
2：代数（必须先修0）
3：语法（必须先修1）
4：几何（必须先修2）
5：写作（必须先修3和4）

这正是上面代码中的例子。运行后你会得到 0 1 2 3 4 5 这样的顺序，表示你可以先学基础数学和基础英语（顺序随意），然后学代数，然后学语法，然后几何，最后写作。你也可以先基础英语再基础数学，只要保证代数在几何之前、语法在写作之前即可。

如果你想自己测试有环的情况，可以故意加一条边，比如让任务5指向任务1（写作必须先于基础英语？），那么图就变成了环（1→3→5→1），程序会输出“存在环，无法拓扑排序”。试试看！

拓扑排序

拓扑排序：给任务排个队，不打架！

核心思想：从“没任何前置任务”的开始

代码一步步拆解

新手容易犯的错误

完整示例：计算课程顺序

相关指引

例题精讲