C++怎么实现拓扑排序检测有向图是否有环-C++-PHP中文网

dfs拓扑排序同步环检测：用三色标记（0/1/2）区分未访问、递归中、已完成状态，遇灰色节点即环；kahn算法通过统计输出节点数是否等于总节点数判环。

c++怎么实现拓扑排序检测有向图是否有环

用 DFS 实现拓扑排序并同步检测环

DFS 是最直观的方案：一边递归遍历，一边用三种状态标记节点（未访问 / 正在访问 / 已完成），只要在「正在访问」状态下再次碰到同一节点，就说明存在环。visited 数组存状态（比如 0 未访问、1 正在访问、2 已完成），递归返回前把当前节点标为 2。

常见错误是只用 bool 类型的 visited，这样无法区分「已回溯完成」和「当前路径中」，导致误判环。也有人忘记在进入递归前设为 1，或忘记在递归后恢复状态（其实不需要恢复，但必须设为 2 表示已处理完毕）。

示例关键逻辑：

vector<int> state(n, 0); // 0: unvisited, 1: visiting, 2: visited
function<bool> dfs = [&](int u) -> bool {
    if (state[u] == 1) return false; // cycle detected
    if (state[u] == 2) return true;  // already processed
    state[u] = 1;
    for (int v : graph[u]) {
        if (!dfs(v)) return false;
    }
    state[u] = 2;
    result.push_back(u); // reverse order
    return true;
};
</bool></int>

用 Kahn 算法做拓扑排序时判断是否成环

Kahn 算法本质是不断剥离入度为 0 的节点。如果最终加入结果的节点数少于图中总节点数，说明剩下节点构成环（因为它们入度永远不为 0）。

注意点：indeg 数组必须初始化正确；队列初始应加入所有 indeg[i] == 0 的节点；每次从队列弹出节点后，要遍历其所有邻接点并更新 indeg[v]--，仅当 indeg[v] == 0 才入队。

性能上，Kahn 是标准 BFS，时间 O(V + E)，空间 O(V + E)，比 DFS 更易调试；但它不记录环的具体路径，只回答「有没有环」。

关键判断代码段：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

queue<int> q;
for (int i = 0; i  topo;
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : graph[u]) {
        if (--indeg[v] == 0) q.push(v);
    }
}
if (topo.size() != n) return false; // has cycle
</int>

邻接表 vs 邻接矩阵对实现的影响

实际写的时候几乎都用邻接表（vector<vector>> graph</vector>），因为稀疏图更常见，且遍历邻居效率高。若用邻接矩阵（vector<vector>> mat</vector>），DFS 中找邻居就得遍历整行，时间退化到 O(V²)；Kahn 中更新入度也要扫整列，同样低效。

另外，输入如果是边列表（如 vector<pair>> edges</pair>），别忘了先建图并统计入度——漏掉某条边会导致 indeg 错误，进而让 Kahn 误判无环。

小提醒：graph[u] 存的是 u 指向的节点，不是反向；Kahn 依赖的入度必须是「指向 u 的边数」，方向弄反是新手高频 bug。