C++拓扑排序怎么找出图中所有入度为0的节点-C++-PHP中文网

直接遍历indegree数组：for (int i = 0; i

怎么用 indegree 数组快速定位所有入度为0的节点

拓扑排序启动前，必须先找出所有入度为0的节点作为起点。最直接的办法是遍历每个节点的入度值——别绕弯子，建好 indegree 数组后，就老老实实扫一遍：
for (int i = 0; i     if (indegree[i] == 0) {<br>        q.push(i); // 或加入 vector<br>    }<br>}
这里 n 是节点总数（不是边数），i 是节点编号（通常从 0 开始）。注意：图可能不连通，所以不能只找一个就停，必须全扫。
为什么不能只靠邻接表反向遍历找入度为0的点

有人想“遍历所有边，把终点标记为‘有入边’，没被标记的就是入度0”，这逻辑看似可行，但容易漏掉孤立节点（即既没出边也没入边的点）。比如节点 5 完全没出现在任何边里，indegree[5] 初始就是 0，但你若只扫描边的终点，根本不会碰到它。

C++ Code Review Master
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

正确做法：indegree 数组必须初始化为 0，再对每条边 u → v 执行 indegree[v]++

孤立节点自动保留在 0 状态，后续扫描自然捕获

邻接表本身不存入边信息，反向遍历成本高且不必要

使用 queue 还是 vector 存初始零入度节点

取决于后续是否需要按顺序处理或支持多源 BFS。拓扑排序标准写法用 queue（如 std::queue 或 std::deque）：

插入和弹出都是 O(1)，适合逐个取出、更新邻居

如果要求字典序最小的拓扑序，得换 std::priority_queue，但此时初始入度为0的节点也要进堆，不能只取最小那个——得全插进去再 pop

单纯收集（比如调试打印所有起点），用 vector 更轻量，也方便遍历

别在初始化阶段做多余排序，除非题目明确要求。
常见错误：图节点编号不连续或从1开始怎么办

实际读图时，节点编号常不连续（如只有 2、5、7、9）或从 1 开始。这时不能硬套 for (int i = 0; i ：<ul> <li>如果已知最大编号 <code>max_id，数组大小设为 max_id + 1，循环范围变成 1 到 max_id（或 0 到 max_id），并确保只检查出现过的节点
更稳妥的做法：用 unordered_set 或布尔数组记录哪些节点真实存在，再结合 indegree 判断

错误示范：for (int i = 0; i ——边数和节点数无关，必然漏节点
入度数组大小错配，是运行时访问越界或逻辑遗漏的高频原因。
拓扑排序中“找所有入度为0节点”这事本身很简单，难点其实在前期建图时是否把每个节点都纳入考虑——尤其是编号稀疏、含孤立点、或输入只给边不给总点数的情况。漏掉一个，整个序就可能不全。