c图论四之有向无环图特的拓扑排序
目录
c++图论(四)之有向无环图特的拓扑排序
在 C++ 中实现有向无环图（DAG，Directed Acyclic Graph）的拓扑排序，可以通过两种经典方法： BFS遍历法 和 DFS 后序遍历 。以下是两种方法的实现原理、代码示例及详细说明：
一、拓扑排序的概念
拓扑排序（Topological Sort）
是将有向无环图中的顶点排列成线性序列，使得对任意边
u → v
，顶点
u
在序列中总出现在
v
之前。
应用场景 ：任务调度、依赖关系管理（如编译顺序）、课程安排等。
二、BFS遍历法
算法步骤
- 计算所有顶点的 入度 （in-degree）。
- 将入度为 0 的顶点加入队列。
- 依次取出队列中的顶点，将其加入拓扑序列，并减少其邻接顶点的入度。若邻接顶点入度减为 0，则加入队列。
- 重复步骤 3，直到队列为空。
- 若拓扑序列包含所有顶点，则排序成功；否则，图中存在环。
模板
// 拓扑排序函数
void toposort() {
for (int i = 1; i <= n; i++)
for (int neighbor : adj[i])
in_degree[neighbor]++; // 计算出所有点入度
queue<int> q;
for (int i = 1; i <= n; i++)
if (in_degree[i] == 0)
q.push(i); // 入度为 0 入队列，顺序无所谓
while (!q.empty()) {
int u = q.front(); q.pop(); // 弹出队首
topo[++t] = u; // 当前点添加至拓扑序列尾部
for (int v : adj[u]) {
in_degree[v]--; // 所有邻居入度减 1
if (in_degree[v] == 0)
q.push(v); // 入度为 0 入队列
}
}
}C++ 实现
// 拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 102
vector<int> adj[MAXN]; // 邻接表
int in_degree[MAXN], n; // 记录入度
int topo[MAXN], t;
// 拓扑排序函数
void toposort() {
for (int i = 1; i <= n; i++) {
for (int neighbor : adj[i]) {
in_degree[neighbor]++;
}
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
topo[++t] = node;
for (int neighbor : adj[node]) {
in_degree[neighbor]--;
if (in_degree[neighbor] == 0) {
q.push(neighbor);
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
while (cin >> x) {
if (x == 0) break;
adj[i].push_back(x);
}
}
toposort();
for (int i = 1; i <= n; i++)
cout << topo[i] << ' ';
return 0;
}三、DFS 后序遍历法
算法步骤
- 对每个未访问的顶点执行 DFS。
- 在 DFS 回溯时，将顶点加入栈中。
- 最终将栈中的顶点依次弹出，得到拓扑序列。
- 需额外检查是否存在环。
模板
vector<int> adj[MAXN]; // 邻接表
// 记录节点状态：
// 1：已经访问完毕
// 0：还没访问过
// -1：正在被访问
int visited[MAXN];
// 数组记录拓扑逻辑的结果，
// 从后往前写，t 指向下一个待写入的位置
int topo[MAXN], t, n;
bool dfs(int u) {
visited[u] = -1; // 访问标志
for (auto v : adj[u])
if (visited[v] < 0) return false; // 存在有向环，失败退出
else if (!visited[v] && !dfs(v)) return false;
visited[u] = 1;
topo[t--] = u;
return true;
}
bool toposort() {
for (int u = 1; u <= n; u++)
if (!visited[u])
if (!dfs(u)) return false;
return true;
}C++ 实现
// 拓扑排序
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 102
vector<int> adj[MAXN]; // 邻接表
// 记录节点状态：
// 1：已经访问完毕
// 0：还没访问过
// -1：正在被访问
int visited[MAXN];
// 数组记录拓扑逻辑的结果，
// 有后往前写，t 指向下一个待写入的位置
int topo[MAXN], t, n;
bool dfs(int u) {
visited[u] = -1; // 访问标志
for (auto v : adj[u])
if (visited[v] < 0) return false; // 存在有向环，失败退出
else if (!visited[v] && !dfs(v)) return false;
visited[u] = 1;
topo[t--] = u;
return true;
}
bool toposort() {
for (int u = 1; u <= n; u++)
if (!visited[u])
if (!dfs(u)) return false;
return true;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
while (cin >> x) {
if (x == 0) break;
adj[i].push_back(x);
}
}
t = n;
toposort();
for (int i = 1; i <= n; i++)
cout << topo[i] << ' ';
return 0;
}四、算法对比及选择
| 特性 | Kahn 算法 | DFS 后序遍历 |
|---|---|---|
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(V)（队列和入度数组） | O(V)（递归栈和标记数组） |
| 检测环 | 天然支持（结果长度 ≠ V 则有环） | 需额外标记回溯路径（ inStack ） |
| 输出顺序 | 依赖入度为 0 的顺序（可能不同） | 逆后序（基于 DFS 完成时间） |
| 适用场景 | 需要即时处理入度为 0 的节点 | 需要逆后序或隐式处理依赖 |
五、总结
- Kahn 算法 ：直观易实现，适合需要按层处理节点的场景，天然支持环检测。
- DFS 后序 ：适合需要逆后序的场景（如任务执行顺序），需显式检查环。
- 实际选择 ：若需即时处理入度为 0 的节点（如实时调度），优先选择 Kahn 算法；若图结构复杂或需要逆后序，选择 DFS 方法。
