c++如何实现拓扑排序算法_c++ 入度统计与AOV网活动调度【案例】

拓扑排序的核心判断条件是图中是否存在环，即遍历结束后输出顶点数是否等于总顶点数；若不等则存在环，排序失败。

拓扑排序的核心判断条件是什么

拓扑排序只适用于有向无环图（DAG）。如果图中存在环，indegree[v] == 0 的节点在某轮遍历后彻底消失，队列/栈变空但仍有未访问节点——此时可直接判定环存在，排序失败。

实际编码中不能只看最终是否输出了全部顶点，必须检查输出顶点数是否等于图中顶点总数。否则就是隐含环，比如输入边 0→1、1→2、2→0 时，所有节点入度始终为 1，queue 从不入队，结果为空。

用 vector> 存邻接表 + indegree 数组怎么写

这是最常用、最易调试的实现方式。邻接表用 vector>，每个 i 对应出边目标列表；入度单独开 vector indegree(n, 0)，初始化时遍历所有边做 indegree[to]++。

注意：顶点编号建议从 0 开始，避免下标越界；若输入是 1-based，读入后统一减 1 处理。

立即学习“C++免费学习笔记（深入）”；

• 使用 queue 实现 BFS 式拓扑序（推荐，顺序稳定）
• 入队前务必检查 indegree[i] == 0，且入队后立即置为 -1 或用布尔数组标记已入队，防止重复入队
• 每次从队首取节点 u，遍历其所有邻接点 v，执行 indegree[v]--；若减到 0，立刻入队

vector> graph(n);
vector indegree(n, 0);
for (auto& e : edges) {
    int u = e[0], v = e[1];
    graph[u].push_back(v);
    indegree[v]++;
}
queue q;
for (int i = 0; i < n; i++)
    if (indegree[i] == 0) q.push(i);

vector topo;
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : graph[u]) {
        indegree[v]--;
        if (indegree[v] == 0) q.push(v);
    }
}
if (topo.size() != n) cout << "cycle detected" << endl;

为什么不能用 DFS 直接递归输出顺序

DFS 版拓扑排序不是简单地在访问时 push_back，而必须在「所有后继都访问完毕」之后才记录当前节点——即使用逆后序（post-order reverse）。否则顺序错乱，例如 A→B、A→C、B→C，DFS 若从 A 入口先走 B 再走 C，可能输出 A,B,C（错误），正确应是 A,B,C 或 A,C,B，但 C 不能在 B 前（因 B→C）。

HaiSnap

一站式AI应用开发和部署工具

下载

常见错误是把 DFS 当成普通遍历，在 visit(u) 开头就加进结果，这实际得到的是某种访问序，不是拓扑序。

• 必须用状态数组区分 unvisited / visiting / visited，遇到 visiting 就说明成环
• 仅当递归返回前（即退出函数前）把 u 加入结果，再 reverse 整个结果
• 多起点时需对每个未访问节点调用 DFS，不能只从 0 开始

AOV 网调度中如何处理多入度依赖与任务权重

AOV 网本身不带权，但实际调度常需扩展：比如任务耗时（权重）、资源约束、或多个前置任务必须全部完成才能开始（这正是入度统计的物理意义）。此时 indegree[u] 就是“还剩几个前置任务未完成”，只有归零才可调度。

若需计算最早开始时间（Earliest Start Time），可在拓扑序上 DP：est[v] = max(est[v], est[u] + duration[u])，前提是图按拓扑序遍历，且 u→v 是依赖边。

• 不要在建图时合并重复边，否则 indegree 统计偏小，导致过早调度
• 若输入含重边（如两个文件都声明依赖同一头文件），需去重或用 set 存邻接表
• 并发调度时，同一轮中所有 indegree==0 的节点可并行执行，这时 queue 可换为 vector 批量处理

入度统计看着简单，但边界全在细节里：初始化漏节点、重边不判、环检测不校验长度、多起点遗漏——这些都会让 AOV 调度在真实项目中静默失败。