当前位置:

首页 > 编程开发 > C++拓扑排序判环方法详解

C++拓扑排序判环方法详解

Kahn算法用std::queue和入度数组实现拓扑排序:建图时记录每条边u→v并统计indeg[v]++,初始化将所有indeg[i]==0的节点入队,每次出队一个点并对其邻接点减入度,减至0则入队;最终若加入拓扑序列的节点数cnt≠总节点数n,则存在环。

本文目录

    Kahn算法用std::queue和入度数组实现拓扑排序:建图时记录每条边u→v并统计indeg[v]++,初始化将所有indeg[i]==0的节点入队,每次出队一个点并对其邻接点减入度,减至0则入队;最终若加入拓扑序列的节点数cnt≠总节点数n,则存在环。

    C++怎么实现拓扑排序检测环_C++DAG判断方法【图论】

    用 std::vector> 建图后怎么跑拓扑排序

    拓扑排序本质是判断 DAG(有向无环图)是否成立,核心动作就是「删入度为 0 的点,更新邻居入度,重复直到删完或卡住」。C++ 里最常用的是 Kahn 算法,依赖 std::queue 和入度数组。

    常见错误现象:queue 为空但还有节点没访问到 → 说明存在环;或者漏初始化入度数组,导致未定义行为。

    • 建图时用 adj[u].push_back(v) 表示边 u → v,同时对每个 v 执行 indeg[v]++
    • indeg 数组大小必须覆盖所有可能的节点编号(比如节点是 1~n,数组就要开 n+1,下标 0 不用也行)
    • 初始把所有 indeg[i] == 0 的 i 入队,哪怕 i 是孤立点(入度出度都为 0)也要算进拓扑序列
    • 每次从队列弹出一个点,对其所有邻接点执行 indeg[v]--,减到 0 就立刻入队

    检测环时为什么不能只看 queue.empty()

    很多人写完 Kahn 就直接检查最后 queue 是否为空,这是错的——queue 只反映“当前可删的点”,不是“是否删完了”。真正判断环的依据是:最终加入拓扑序列的节点数是否等于总节点数。

    使用场景:你传入了 n 个节点,但图里实际只出现过其中一部分编号(比如只有 0、2、4),这时要小心「未出现的节点是否该计入总数」。通常约定:输入明确给出节点范围 [0, n) 或 [1, n],就以 n 为准。

    • 维护一个计数器 cnt,每弹出一个点就 cnt++
    • 循环结束后,cnt != n 就代表有环
    • 别用 queue.size() == 0 && cnt < n 当判断条件——队列空是常态,不意味着结束

    std::stack 替换 std::queue 会影响环检测结果吗

    不影响。Kahn 算法中用栈还是队列,只改变拓扑序的输出顺序(DFS-like vs BFS-like),不改变「能否遍历全部节点」这个事实。环的存在性是图的固有属性,和遍历容器无关。

    性能影响:栈在缓存局部性上略好,但差别微乎其微;兼容性无差异,都是标准容器。

    • 如果用 std::stack,记得用 s.top()/s.pop(),别误用 front()
    • 不要以为“栈=DFS”就自动支持环检测回溯——Kahn 本身不含递归或回溯逻辑
    • 某些 OJ 题目要求字典序最小的拓扑序,这时得用 std::priority_queue,但那是另一回事,和环检测无关

    用 DFS 实现环检测时 visited 要分三种状态

    DFS 版本不生成拓扑序,只判环,但更贴近直觉:遇到正在递归中的节点,就说明成环。关键在于 visited 不能只是 bool,必须区分「未访问」「访问中」「已访问完」。

    错误现象:仅用 bool visited[],会把反向边(back edge)误判为环;或者漏掉跨连通分量的环(其实不会,但状态不清会导致逻辑混乱)。

    • 推荐用 vector state(n, 0):0 = 未访问,1 = 访问中(在当前 DFS 栈上),2 = 已完成
    • 进入 DFS 前设 state[u] = 1,返回前设 state[u] = 2
    • 遇到邻居 v 且 state[v] == 1 → 立刻返回 true(发现环)
    • 注意:必须对每个未访问节点都调用 DFS,不能只从 0 开始——图可能不连通
    拓扑排序检测环这件事,难点不在代码长短,而在于对「入度清零」和「DFS 栈帧活性」这两个抽象概念的准确映射。稍不注意,indeg 数组越界、状态变量复用、节点编号与数组下标错位,都会让结果看起来“偶尔对偶尔错”。
    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    Codex 0.170.0-alpha.4.1 预发行如何关闭 Bedrock 增量工具声明?
    Codex 0.170.0-alpha.4.1 预发行如何关闭 Bedrock 增量工具声明?

    Codex 0.170.0-alpha.4.1 预发行默认在两种 Amazon Bedrock provider 上走增量工具定义,保留显式关闭选项。

    Codex 0.171.0-alpha.11 的侧栏怎样呈现会话文件与图片?
    Codex 0.171.0-alpha.11 的侧栏怎样呈现会话文件与图片?

    Codex 0.171.0-alpha.11 为终端侧栏增加会话文件入口和图片预览。选择器负责发现文件,预览根据文件类型和终端能力决定显示方式。

    Codex 0.171.0-alpha.8 预发行的远程执行和线程恢复怎么用?
    Codex 0.171.0-alpha.8 预发行的远程执行和线程恢复怎么用?

    Codex 0.171.0-alpha.8 预发行允许 exec 连接现有应用服务器,说明 WebSocket 认证、服务端配置与线程恢复限制。

    Cursor 的 Hospitable 1.0.0 怎么分清日历查询和预订修改?
    Cursor 的 Hospitable 1.0.0 怎么分清日历查询和预订修改?

    从 Cursor 3.13.0 起可添加 Hospitable 1.0.0 插件,检查只查、编辑、取消和发送住客消息的适用条件。

    Cursor Close 插件 1.0.0 的只读、安全写入和删除权限怎么区分?
    Cursor Close 插件 1.0.0 的只读、安全写入和删除权限怎么区分?

    Cursor Close 插件 1.0.0 要求 Cursor 3.13.0 起,说明聊天添加命令、单组织连接以及三种账号授权范围。 Cursor 的 Close 1.0.0 把查询、创建和更新删除分到三个授权等级。只需要查看线索时,只读授权能覆盖查询场景。

    Cursor Redo 插件 1.0.0 如何理解店铺接入和退货操作权限?
    Cursor Redo 插件 1.0.0 如何理解店铺接入和退货操作权限?

    Cursor Redo 插件 1.0.0 要求 Cursor 3.13.0 起,说明聊天添加命令、商家授权及订单查询与退货写入的区别。 Redo 1.0.0 可通过 Cursor 添加到商家工作环境。接入后,订单查询与退货处理取决于对应的店铺账号和角色。

    Qwen Code TypeScript SDK v0.1.35 和 CLI v0.28.0 有什么关系?
    Qwen Code TypeScript SDK v0.1.35 和 CLI v0.28.0 有什么关系?

    Qwen Code TypeScript SDK v0.1.35 正式版同捆 CLI v0.28.0,适用 Node.js 22.0.0 以上,安装状态以 npm 注册表为准。

    llama.cpp b12470 修复了哪些 SYCL Flash Attention 掩码广播错误?
    llama.cpp b12470 修复了哪些 SYCL Flash Attention 掩码广播错误?

    llama.cpp b12470 预发布构建修复了 SYCL 后端使用 MKL 的 Flash Attention 路径。掩码按注意力头或批次广播时,会避免对较小掩码维度直接越界读取。

    Qwen Code v0.28.0 默认在哪些场景启用共享 Agent 循环?
    Qwen Code v0.28.0 默认在哪些场景启用共享 Agent 循环?

    Qwen Code v0.28.0 将共享 Agent 循环默认用于无界面会话、Ink 终端和子代理。各入口在没有显式配置时采用自己的默认值。

    n8n 2.49.0 与 3.3.0 预发布版如何保存和隔离工具调用记录?
    n8n 2.49.0 与 3.3.0 预发布版如何保存和隔离工具调用记录?

    n8n 2.49.0 与 3.3.0 预发布版对 AI Agent 作了三处调整。工具调用前的模型文本进入 Agent 历史,每条输入单独保存工具调用历史,一次对话中的每轮工具调用都写入聊天记忆。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。