1. 拓扑排序：从依赖关系到执行序列

在软件工程、项目管理乃至日常的学习计划制定中，我们常常会遇到一个经典问题：有一系列任务，其中某些任务必须在另一些任务完成之后才能开始。如何找到一个合理的顺序，使得所有任务都能在不违反依赖关系的前提下被完成？这个问题在计算机科学中有一个优雅而强大的解决方案——拓扑排序。

拓扑排序是图论中的一个核心算法，专门用于处理有向无环图（DAG）中节点的线性排序问题。它的核心思想非常直观：如果图中存在一条从节点A指向节点B的边（A -> B），那么在排序结果中，节点A必须出现在节点B之前。这个特性完美契合了“依赖关系”的描述。因此，拓扑排序不仅是算法竞赛中的常客，更是解决实际工程中任务调度、编译顺序确定、课程安排等问题的利器。

很多人初次接触拓扑排序时，会觉得它概念清晰但实现起来有些抽象，或者记住了模板却不知道如何应用到具体问题中。这篇内容，我将结合自己多年的算法工程经验，从拓扑排序的核心思想、两种经典实现模板（Kahn算法和基于DFS的算法）入手，再通过几个由浅入深的实战例题，带你彻底掌握这个工具。无论你是正在准备算法面试的学生，还是需要处理复杂依赖关系的开发者，相信都能从中获得可以直接“抄作业”的干货。

2. 拓扑排序的核心思想与前置知识

在深入代码之前，我们必须先夯实理论基础。拓扑排序并非凭空产生，它建立在坚实的图论基础之上，理解其约束条件和应用场景是灵活运用的前提。

2.1 什么是有向无环图（DAG）？

拓扑排序的对象必须是有向无环图。这三个定语缺一不可：

1. 有向：图中的边具有方向性，即从节点A到节点B的边（A->B）与从B到A的边（B->A）是两条不同的边。这清晰地表示了依赖关系的方向。
2. 无环：图中不能存在任何形式的环路。这意味着不存在一条路径，使得从一个节点出发，沿着有向边行走，最终又能回到该节点。环路的存在意味着依赖关系形成了“死锁”，例如任务A依赖B，B依赖C，C又依赖A，这将导致无法找到合法的执行顺序。
3. 图：由节点（或顶点）和连接节点的边组成的数据结构。

注意：判断一个图是否为DAG是进行拓扑排序的第一步。如果图中存在环，则拓扑排序无法得到完整的结果（通常只能输出部分节点，或者算法会明确指出存在环）。后续我们会看到，拓扑排序算法本身也可以作为一种高效的环检测手段。

2.2 入度与出度：理解节点状态的关键

在图论中，入度和出度是描述节点连接情况的核心指标，对于拓扑排序的实现至关重要。

• 入度：指向该节点的边的数量。它代表了“有多少个前置任务依赖于此任务完成”。入度为0的节点意味着没有任何前置约束，可以立即执行。
• 出度：从该节点指出的边的数量。它代表了“此任务完成后，可以解锁多少个后续任务”。

在拓扑排序的过程中，我们主要关注入度。算法的核心动作之一就是不断地寻找并将当前入度为0的节点加入结果序列，然后“移除”它，并更新其所有邻居节点的入度。

2.3 拓扑排序的结果不唯一

这是一个非常重要的特性。对于一个DAG，其拓扑排序的结果可能有多种。例如，有三个任务A、B、C，依赖关系为A->C, B->C（即C依赖A和B）。那么[A, B, C]和[B, A, C]都是合法的拓扑排序。只要满足所有边的方向性要求，排序就是有效的。某些题目会要求输出字典序最小或最大的序列，这通常需要通过维护一个优先队列而不是普通队列来实现。

3. 拓扑排序的两种经典实现模板

掌握了思想，我们来看如何用代码实现。主要有两种广为人知的算法：Kahn算法（基于BFS）和基于DFS的算法。两者各有优劣，适用于不同场景。

3.1 Kahn算法（BFS/队列实现）

这是最直观、最常用的方法，其过程模拟了“不断完成可执行任务”的现实场景。

算法步骤：

1. 初始化：计算图中每个节点的入度，并准备一个队列（或优先队列）。
2. 寻找起点：将所有入度为0的节点放入队列。这些是当前可以立即执行的“任务”。
3. 处理节点： a. 从队列中取出一个节点，将其加入拓扑排序的结果序列。 b. “移除”该节点：遍历该节点的所有后继节点（邻居），将每个后继节点的入度减1。 c. 检查减1后，是否有后继节点的入度变为0。如果有，则将其加入队列。
4. 重复与判断：重复步骤3，直到队列为空。
5. 结果验证：检查结果序列的长度是否等于图中节点的总数。
   • 如果相等，说明排序成功，该序列即为一个拓扑序。
   • 如果不相等，说明图中存在环，无法完成拓扑排序。

模板代码（C++）：

#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> topologicalSort(int n, vector<vector<int>>& graph) { vector<int> inDegree(n, 0); vector<int> result; queue<int> q; // 1. 计算每个节点的入度 for (int u = 0; u < n; ++u) { for (int v : graph[u]) { inDegree[v]++; } } // 2. 将所有入度为0的节点入队 for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) { q.push(i); } } // 3. BFS过程 while (!q.empty()) { int u = q.front(); q.pop(); result.push_back(u); // 加入结果 // “移除”当前节点，更新其后继节点的入度 for (int v : graph[u]) { inDegree[v]--; if (inDegree[v] == 0) { q.push(v); } } } // 4. 判断是否有环 if (result.size() != n) { // 图中存在环，返回空数组或根据题目要求处理 return {}; } return result; }

Kahn算法特点与心得：

• 直观易懂：过程模拟了现实的任务调度，逻辑清晰。
• 便于检测环：通过比较结果序列长度和节点总数，可以轻松判断图中是否有环。
• 天然适合求“排序序列”：结果就是节点出队的顺序。
• 实战技巧：如果需要字典序最小的拓扑序，只需将普通队列queue替换为优先队列priority_queue<int, vector<int>, greater<int>>（小顶堆）即可。这样每次都会取出当前可执行节点中编号最小的那个。

3.2 基于DFS的算法

这种方法利用深度优先搜索的递归特性，在回溯时记录节点，其逆序即为一个拓扑排序。

算法步骤：

1. 任选一个未访问的节点开始DFS。
2. 在DFS过程中，首先递归访问它的所有后继节点。
3. 当从一个节点的所有后继节点都返回后，将该节点加入一个栈中。
4. 重复1-3，直到所有节点都被访问。
5. 最后，将栈中的节点依次弹出，得到的序列就是一个拓扑排序。

模板代码（C++）：

#include <iostream> #include <vector> #include <stack> using namespace std; bool dfs(int u, vector<int>& visited, vector<vector<int>>& graph, stack<int>& stk) { visited[u] = 1; // 标记为“正在访问” for (int v : graph[u]) { if (visited[v] == 1) { return false; // 发现环 } if (visited[v] == 0) { if (!dfs(v, visited, graph, stk)) { return false; } } } visited[u] = 2; // 标记为“已访问完成” stk.push(u); return true; } vector<int> topologicalSortDFS(int n, vector<vector<int>>& graph) { vector<int> visited(n, 0); // 0=未访问，1=访问中，2=已访问 stack<int> stk; vector<int> result; for (int i = 0; i < n; ++i) { if (visited[i] == 0) { if (!dfs(i, visited, graph, stk)) { return {}; // 发现环 } } } while (!stk.empty()) { result.push_back(stk.top()); stk.pop(); } return result; }

DFS算法特点与心得：

• 适合求“拓扑排序是否存在”或特定需求：DFS在递归过程中可以方便地加入其他逻辑。
• 天然的环检测：通过三色标记法（0未访问，1访问中，2已访问），如果在访问中状态（1）再次遇到同一个节点，立刻就能判断存在环，无需等到最后。
• 结果需要反转：得到的栈是“后续节点先入栈”，弹出时顺序正好是拓扑序。
• 注意递归深度：对于节点数非常多（例如超过10^5）的图，递归实现的DFS可能导致栈溢出。此时需要考虑使用栈模拟递归，或者优先使用Kahn算法。

两种算法如何选择？

• 大多数情况下，推荐使用Kahn算法。它更直观，代码不易出错，且利用队列易于实现字典序等额外要求。
• 当问题需要在DFS过程中嵌入复杂逻辑（例如，在拓扑排序的同时进行动态规划）时，可以考虑DFS方法。
• 如果题目明确要求判断环，两种方法都可以，Kahn算法判断更简洁。

4. 实战例题解析：从应用到变式

理解了模板，我们通过几道经典例题来看看拓扑排序如何解决实际问题。我会从问题分析、代码实现到易错点，一步步拆解。

4.1 例题一：课程表（LeetCode 207）

问题描述：你需要选修numCourses门课程，记为0到numCourses-1。在选修某些课程之前需要先修一些课程。先修关系由数组prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则必须先学习课程bi。请你判断是否可能完成所有课程的学习。

分析：这正是拓扑排序的典型应用。课程是节点，先修关系[ai, bi]构成一条从bi指向ai的有向边。问题等价于判断这个课程关系图是否是一个DAG（有向无环图）。如果能完成拓扑排序（即排序结果包含所有课程），则可能完成所有课程；否则，意味着存在循环依赖（环），无法完成。

解题思路：直接套用Kahn算法模板。

1. 建图，并计算每个课程的入度。
2. 将入度为0的课程入队。
3. 执行BFS，每完成一门课（出队），就将其后续课程的入度减1，并将新的入度为0的课程入队。
4. 统计成功出队（完成）的课程数量。如果数量等于总课程数，返回true，否则返回false。

代码实现：

class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> graph(numCourses); vector<int> inDegree(numCourses, 0); // 1. 建图并计算入度 for (auto& p : prerequisites) { int course = p[0], pre = p[1]; graph[pre].push_back(course); // pre -> course inDegree[course]++; } // 2. 初始化队列 queue<int> q; for (int i = 0; i < numCourses; ++i) { if (inDegree[i] == 0) q.push(i); } // 3. BFS拓扑排序 int count = 0; while (!q.empty()) { int u = q.front(); q.pop(); count++; for (int v : graph[u]) { if (--inDegree[v] == 0) { q.push(v); } } } // 4. 判断是否所有课程都能完成 return count == numCourses; } };

避坑指南：

• 建图方向：务必看清依赖关系。题目是[ai, bi]表示学ai前需学bi，所以边是bi -> ai。如果建反了，整个逻辑就错了。
• 索引从0开始：课程编号是0到n-1，使用数组存储入度和图时，大小就是numCourses，直接下标访问，不要自己减1。

4.2 例题二：课程表 II（LeetCode 210）

问题描述：在上一题的基础上，不仅要求判断能否完成，还需要返回一个完成所有课程的学习顺序（任意一种即可）。如果不可能完成，返回空数组。

分析：这几乎是上一题的“标准输出”版本。我们不再仅仅计数，而是需要记录出队的顺序。

解题思路：在Kahn算法的BFS循环中，将出队的节点依次存入结果数组即可。

代码实现（改动部分）：

class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> graph(numCourses); vector<int> inDegree(numCourses, 0); vector<int> result; // 用于存储拓扑序 // 建图、计算入度（同例题一） for (auto& p : prerequisites) { graph[p[1]].push_back(p[0]); inDegree[p[0]]++; } queue<int> q; for (int i = 0; i < numCourses; ++i) { if (inDegree[i] == 0) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); result.push_back(u); // 记录顺序 for (int v : graph[u]) { if (--inDegree[v] == 0) { q.push(v); } } } // 判断并返回结果 if (result.size() == numCourses) { return result; } else { return {}; } } };

心得：这两道题是拓扑排序的“敲门砖”，务必做到能闭着眼睛写出来。它们清晰地展示了拓扑排序解决依赖问题的核心流程。

4.3 例题三：火星词典（LeetCode 269 / 剑指 Offer II 114）

问题描述：现有一种使用外星字母表的外星语言，这门语言的字母顺序与英语顺序不同。给定一个字符串列表words，这些单词是根据这种外星语言的字典序排列的。请你根据该列表推断出外星语言字母的顺序。如果顺序无效（即words不是按此外星语言的字典序排列的），返回空字符串。如果存在多种可能的顺序，返回任意一种即可。

分析：这是一个将拓扑排序应用于“自定义排序规则推导”的经典问题。难点在于如何从给定的单词序列中提取出字母之间的依赖关系（边）。

• 比较相邻的两个单词word1和word2。
• 找到第一个不同的字符c1和c2。那么，根据字典序定义，字符c1应该排在字符c2之前。这就构成了一条边c1 -> c2。
• 如果word2是word1的前缀（例如"abc"和"ab"），那么这是无效的，因为短的前缀不可能排在长的单词后面。应直接返回空字符串。
• 收集所有这样的边，构建一个有向图，节点是出现过的所有字母。
• 对这个图进行拓扑排序，得到的序列就是一种可能的字母顺序。

解题步骤：

1. 初始化图、入度表（由于字母是字符，可以用Map或大小为26的数组，假设只有小写字母）。
2. 遍历words，比较每对相邻单词，提取边并更新图和入度。处理无效情况。
3. 对构建的图执行拓扑排序（Kahn算法）。
4. 检查排序结果是否包含了所有出现的字母。如果是，返回结果字符串；否则，说明有环或逻辑矛盾，返回空串。

代码实现：

class Solution { public: string alienOrder(vector<string>& words) { unordered_map<char, unordered_set<char>> graph; // 邻接表 unordered_map<char, int> inDegree; // 入度表 string result; // 初始化所有出现的字母，入度为0 for (string& word : words) { for (char c : word) { inDegree[c] = 0; // 确保所有字母都在入度表中 } } // 构建图 for (int i = 0; i < words.size() - 1; ++i) { string& w1 = words[i]; string& w2 = words[i + 1]; int len = min(w1.length(), w2.length()); bool foundDiff = false; for (int j = 0; j < len; ++j) { char c1 = w1[j], c2 = w2[j]; if (c1 != c2) { // 找到第一个不同字符，建立边 c1 -> c2 if (!graph[c1].count(c2)) { // 避免重复边增加入度 graph[c1].insert(c2); inDegree[c2]++; } foundDiff = true; break; // 只取第一个不同字符 } } // 特殊情况：w2是w1的前缀，且w1更长，无效 if (!foundDiff && w1.length() > w2.length()) { return ""; } } // Kahn算法拓扑排序 queue<char> q; for (auto& [ch, deg] : inDegree) { if (deg == 0) q.push(ch); } while (!q.empty()) { char u = q.front(); q.pop(); result.push_back(u); for (char v : graph[u]) { if (--inDegree[v] == 0) { q.push(v); } } } // 如果结果长度等于字母总数，说明成功 return result.length() == inDegree.size() ? result : ""; } };

难点与技巧：

• 去重边：两个单词间只能提取一条有效的边（第一个不同字符）。必须检查graph[c1]中是否已存在c2，否则可能重复增加c2的入度，导致结果错误。这里使用unordered_set存储邻接节点就是为了方便去重。
• 无效情况处理：“abc”排在“ab”前面是绝对错误的，需要提前返回。这是本题的一个关键边界条件。
• 数据结构选择：因为字母是有限的（题目常规定为小写字母），也可以使用vector<vector<int>> graph(26)和vector<int> inDegree(26, -1)（用-1表示字母未出现）来提高效率。但使用Map更通用，代码也更清晰。

4.4 例题四：并行课程 III（LeetCode 2050）

问题描述：有n门课程，编号从1到n。给你一个整数n和一个二维整数数组relations，其中relations[j] = [prevCourse_j, nextCourse_j]表示课程prevCourse_j必须在课程nextCourse_j之前完成。同时给你一个下标从0开始的整数数组time，其中time[i]表示完成第(i+1)门课程需要花费的月份数。请你计算完成所有课程所需的最少月份数。你可以同时上任意数量的课程，只要满足先修条件。

分析：这道题在拓扑排序的基础上，增加了动态规划的思想。它要求的是完成所有课程的最短时间，而不是简单的顺序。由于可以并行学习，所以总时间取决于最长的那个任务链（关键路径）。

• 对于一门课程i，它的最早完成时间finishTime[i]等于它所有先修课程中最晚的完成时间，再加上它自身的学习时间time[i-1]。
• 即：finishTime[i] = max(finishTime[pre]) + time[i-1]，其中pre是i的所有先修课程。
• 最终的答案就是所有finishTime[i]中的最大值。

解题思路：拓扑排序是处理这种依赖关系的天然框架。我们按照拓扑序依次处理课程，当处理到一门课程时，它的所有先修课程一定已经被处理过了（因为先修课程的入度先变为0，先出队），此时我们可以安全地计算它的完成时间。

算法步骤：

1. 建图（注意课程编号从1开始，代码中通常转为0-based），计算入度。
2. 初始化一个队列，将所有入度为0的课程入队。同时，初始化一个finishTime数组，对于这些入度为0的课程，它们的完成时间就是自身的学习时间。
3. 进行BFS拓扑排序。对于出队的课程u，遍历其所有后继课程v： a. 更新finishTime[v] = max(finishTime[v], finishTime[u] + time[v-1])。因为v可能有多个先修课程，我们要取最晚的那个。 b. 将v的入度减1。如果减为0，则将v入队。此时finishTime[v]已经计算完成（因为所有先修课程都处理完了）。
4. 遍历结束后，finishTime数组中的最大值即为答案。

代码实现：

class Solution { public: int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) { vector<vector<int>> graph(n + 1); // 课程编号1-n，多开一个空间 vector<int> inDegree(n + 1, 0); vector<int> finishTime(n + 1, 0); // 1. 建图，计算入度 for (auto& rel : relations) { int prev = rel[0], next = rel[1]; graph[prev].push_back(next); inDegree[next]++; } // 2. 初始化队列和完成时间 queue<int> q; for (int i = 1; i <= n; ++i) { if (inDegree[i] == 0) { q.push(i); finishTime[i] = time[i - 1]; // 无先修课，完成时间即自身耗时 } } int ans = 0; // 3. 拓扑排序 + DP while (!q.empty()) { int u = q.front(); q.pop(); ans = max(ans, finishTime[u]); // 更新全局最大时间 for (int v : graph[u]) { // 关键：用当前课程u的完成时间，去更新后继课程v的最晚开始时间 finishTime[v] = max(finishTime[v], finishTime[u] + time[v - 1]); if (--inDegree[v] == 0) { q.push(v); } } } return ans; } };

核心要点：

• 拓扑序与DP的结合：拓扑排序保证了当我们计算一门课程时，其所有前驱课程的最早完成时间都已经确定。这使得我们可以进行递推式的动态规划。
• 状态定义：finishTime[i]表示完成课程i所需的最早时间（月份）。
• 状态转移：finishTime[v] = max(所有finishTime[u]) + time[v-1]，其中u是v的直接前驱。这个max操作体现了“必须等所有先修课都完成”的约束。
• 初始化：入度为0的课程，其finishTime初始化为自身的学习时间。
• 答案：所有课程完成时间中的最大值，因为整个项目（所有课程）的结束时间取决于最慢的那条路径。

这道题完美展示了拓扑排序如何作为骨架，与其他算法思想（如动态规划）结合，解决更复杂的调度和规划问题。

5. 常见问题与排查技巧实录

在实际编码和解题中，即使理解了算法，也难免会遇到各种“坑”。下面是我总结的一些常见问题和排查技巧。

5.1 如何判断图是否有环？

这是拓扑排序最基本也是最重要的衍生功能。

• Kahn算法：在算法结束后，检查拓扑排序结果序列的长度是否等于节点总数n。如果result.size() < n，则说明有环。因为环上的节点入度永远不会减到0，无法进入队列。
• DFS算法：使用三色标记法。在递归访问过程中，如果发现某个邻居节点的状态是“访问中”（visited[v] == 1），则立刻检测到环，可以提前返回。

心得：在需要判断环的题目中，我通常首选Kahn算法，因为判断逻辑简单直接（比较大小），不易出错。

5.2 为什么我的拓扑排序结果不对？

可以从以下几个方向排查：

1. 建图方向错误：这是最常见的原因！务必仔细阅读题目，明确边的方向代表什么依赖关系。是A依赖B建边B->A，还是A先于B建边A->B？画一个小例子验证一下。
2. 入度计算错误：建图时，增加后继节点入度的操作必须和边的方向对应。如果边是u->v，那么应该是inDegree[v]++。
3. 重复边导致入度异常：像“火星词典”那样的题目，如果不处理重复边，会导致某些节点的入度被多次增加，从而无法在正确时机变为0。在建图时，如果题目没有明确说明没有重边，需要考虑去重。
4. 初始化队列遗漏：确保所有入度为0的节点在开始时都加入了队列。一个检查方法是遍历inDegree数组。
5. 节点编号处理：题目给出的节点编号是1-based还是0-based？你的数组大小和访问索引是否正确？这是一个低级但容易致命的错误。

5.3 需要输出所有拓扑排序结果怎么办？

标准的Kahn算法一次只能得到一个拓扑序。如果需要输出所有可能的拓扑序，必须使用回溯法。

• 在每一步，不是从队列中取一个节点，而是从当前所有入度为0的节点集合中依次选择。
• 每选择一个节点，就将其加入当前路径，并“移除”它（更新其后继节点入度），然后递归地进行下一步。
• 递归返回后，需要“恢复”现场（将该节点加回入度为0的集合，并恢复其后继节点的入度），以便尝试下一个选择。
• 这实际上是一种基于BFS思想的DFS回溯，时间复杂度较高，适用于节点数较少（如n<=10）的情况。

5.4 拓扑排序与BFS/DFS的关系

• Kahn算法本质是BFS：它使用队列，一层层地处理入度为0的节点。
• 另一种算法本质是DFS：通过递归深入优先访问后代，在回溯时记录顺序。
• 两者都可以用来拓扑排序和检测环，只是视角不同。BFS版本更侧重于“从起点开始扩散”，DFS版本更侧重于“深入探索再回溯”。

5.5 性能优化与注意事项

• 稠密图与稀疏图：使用邻接表（vector<vector<int>>）存储图对于稀疏图更节省空间。对于已知节点数且范围不大的情况（如26个字母），使用二维数组或vector< bitset >也是可行的。
• 优先队列维护字典序：当需要输出特定顺序（如字典序最小）的拓扑序时，将Kahn算法中的普通队列queue替换为优先队列priority_queue即可。小顶堆得到最小字典序，大顶堆得到最大字典序。
• 递归深度：基于DFS的实现在节点数极大时可能引发栈溢出。在竞赛或工程中，如果节点数超过10^4量级，要谨慎使用递归DFS，可以考虑显式栈或直接使用Kahn算法。
• 动态图拓扑排序：如果图是动态变化的（边会添加或删除），维护拓扑序会变得复杂。通常需要额外数据结构来高效更新入度和检测环，这类问题难度会大大增加。

拓扑排序是一个原理清晰、应用广泛的算法。掌握其核心在于理解“入度”和“依赖关系”的对应，以及Kahn算法那个简洁而优美的队列处理过程。从简单的课程表，到复杂的项目调度、编译顺序，再到像火星词典这样的抽象问题，其内核都是一致的。多练习，多思考不同问题如何转化为图上的依赖关系，你就能越来越熟练地运用这个强大的工具。