前序文章：拓扑排序 - C++目录 - 青少年编程知识记录

一、简述

二、核心概念

1. 1.入度（In-degree）对于顶点 v，入度是指所有以 v 为终点的有向边的数量，记为in_degree[v]。

• 入度为 0 的顶点，没有前驱节点，可以作为拓扑排序的起点。

2. 2.有向无环图（DAG）拓扑排序的前提条件，如果图中存在环，则无法进行拓扑排序（环内节点互相依赖，无法确定先后顺序）。

三、实现算法

1. 卡恩算法（Kahn's Algorithm）—— 基于入度的贪心算法

核心思想

（1）初始化一个队列，将所有入度为 0 的顶点加入队列。

（2）循环从队列中取出顶点 u，加入拓扑序列，并遍历 u 的所有邻接顶点 v：

• 将 v 的入度减 1（ 相当于移除边u——>v) ）。

• 如果 v 的入度变为 0，则将 v 加入队列。

（3）重复上述步骤，直到队列为空。

（4）若最终拓扑序列的长度等于图中顶点总数，则排序成功；否则图中存在环。

复杂度分析

• 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数（每个顶点和边仅被处理一次）。

• 空间复杂度：O(V)（入度数组、队列、结果数组）。

参考代码

#include <iostream>  #include <vector>  #include <queue>  using namespace std;  // 拓扑排序：Kahn算法  // 参数：n-顶点数，adj-邻接表，返回拓扑序列（空表示存在环）  vector<int> kahn(int n, vector<vector<int>>& adj) {      vector<int> in_degree(n, 0); // 记录每个顶点的入度      vector<int> result;          // 存储拓扑序列      queue<int> q;                // 存放入度为0的顶点      // 1. 统计每个顶点的入度      for (int u = 0; u < n; u++) {          for (int v : adj[u]) {              in_degree[v]++;          }      }      // 2. 初始化队列：入度为0的顶点入队      for (int i = 0; i < n; i++) {          if (in_degree[i] == 0) {              q.push(i);          }      }      // 3. 处理队列中的顶点      while (!q.empty()) {          int u = q.front();          q.pop();          result.push_back(u); // 加入拓扑序列          // 遍历u的邻接顶点，减少入度          for (int v : adj[u]) {              in_degree[v]--;              if (in_degree[v] == 0) { // 入度为0时入队                  q.push(v);              }          }      }      // 4. 检查是否存在环：若结果长度≠顶点数，说明有环      if (result.size() != n) {          return {}; // 空数组表示存在环      }      return result;   }    // 测试样例  int main() {      int n = 6; // 顶点数（0~5）      vector<vector<int>> adj(n);      // 构建有向边：0→1, 0→2, 1→3, 2→3, 3→4, 3→5      adj[0].push_back(1);      adj[0].push_back(2);      adj[1].push_back(3);      adj[2].push_back(3);      adj[3].push_back(4);      adj[3].push_back(5);      vector<int> topo = kahn(n, adj);      cout<<topo.size()<<endl;       if (topo.empty()) {          cout << "图中存在环，无法拓扑排序！" << endl;      } else {          cout << "拓扑序列：";          for (int v : topo) {              cout << v << " ";          }          // 可能的输出：0 1 2 3 4 5  或  0 2 1 3 5 4 等      }      return 0;  }

2. 基于 DFS 的拓扑排序

核心思想

• (1)对图进行深度优先搜索（DFS），在访问完一个顶点的所有邻接顶点后，将该顶点加入栈。

• (2)所有顶点处理完成后，依次弹出栈顶元素，得到的序列就是拓扑序列。

• (3)原理：DFS 会先遍历完顶点的所有后继节点，因此当前顶点可以 “后入栈、先出栈”，满足拓扑顺序。

注意事项

• 该方法无法直接检测环，需要额外添加一个 onStack 数组标记当前递归栈中的顶点：若在 DFS 中遇到 onStack[v] = true 的顶点，说明存在环。

• 复杂度与 Kahn 算法相同：O(V + E)。

参考代码

#include <iostream>  #include <vector>  #include <stack>  using namespace std;    // 标记顶点是否被访问，避免重复遍历  vector<bool> visited;  stack<int> stk; // 存储顶点，用于生成拓扑序列    // DFS 遍历函数  void dfs(int u, vector<vector<int>>& adj) {      visited[u] = true; // 标记当前顶点已访问      // 遍历u的所有邻接顶点      for (int v : adj[u]) {          if (!visited[v]) { // 未访问过的顶点递归DFS              dfs(v, adj);          }      }      // 所有邻接顶点处理完后，当前顶点入栈      stk.push(u);  }    // 拓扑排序：基于DFS  vector<int>DFS(int n, vector<vector<int>>& adj) {      visited.assign(n, false); // 初始化访问标记      // 遍历所有顶点，处理非连通图的情况      for (int i = 0; i < n; i++) {          if (!visited[i]) {              dfs(i, adj);          }      }      // 栈中元素出栈，得到拓扑序列      vector<int> result;      while (!stk.empty()) {          result.push_back(stk.top());          stk.pop();      }      return result;  }    int main() {      int n = 6;      vector<vector<int>> adj(n);      adj[0].push_back(1);      adj[0].push_back(2);      adj[1].push_back(3);      adj[2].push_back(3);      adj[3].push_back(4);      adj[3].push_back(5);        vector<int> topo = DFS(n, adj);      cout << "拓扑序列（DFS版）：";      for (int v : topo) {          cout << v << " ";      }      return 0;  }

三、典型应用场景

1. 任务调度：比如编译时的依赖关系（先编译被依赖的文件）、项目管理中的任务先后顺序。

2. 课程安排：大学选课系统中，先修课程必须在后续课程前完成。

3. 依赖解析：包管理器（如 npm、Maven）安装依赖时，按依赖顺序安装包。

四、关键结论

1. 拓扑排序仅适用于 DAG，有环图无法拓扑排序。

2. 拓扑序列不唯一，不同算法或不同起点可能得到不同的合法序列。

3. Kahn 算法的优势是可以检测环，且实现直观；DFS 算法更适合处理非连通图的拓扑排序。