C++实现图的拓扑排序(Kahn算法) _ 入度统计法与BFS核心算法实现【源码】
拓扑排序失败常因图中存在环路依赖。需确保入度数组正确初始化为零，避免残留随机值。邻接表构建方向必须为u指向v，BFS更新入度时需在弹出节点后立即处理其后继节点。若结果序列长度小于节点总数，则表明图中存在环。算法需显式处理环路情况。
拓扑排序失败，这事儿在算法实现里挺常见的。表面上看，代码逻辑似乎都对，但一运行，要么卡住不动，要么输出的序列长度不对，就是排不出一个完整的顺序。问题的根源，十有八九是图中存在环路依赖，导致算法找不到那个“零依赖”的起始节点，整个流程就卡壳了。
具体是哪些环节容易出岔子呢？咱们来逐一排查。
为什么拓扑排序失败？先检查入度数组是否初始化为0
如果你的拓扑排序卡在空队列或者提前退出了，第一个要怀疑的就是 inDegree 数组有没有被正确清零。在C++里，用 vector 来初始化是相对安全的做法。但如果你用的是裸数组，比如 int inDegree[1000]，却忘了用 memset 或者 std::fill 来初始化，那么数组里残留的随机值就会被误当成某些节点的入度。结果就是，这些节点可能永远达不到入度为0的条件，进不了队列，整个排序流程自然就中断了。
一个典型的错误现象是：最终得到的 result.size() 不等于节点总数 n，但程序又不报错。调试的时候仔细看，可能会发现某个节点的 inDegree[v] 显示为一个非常大的随机数。
- 优先使用
vector容器，它能帮你省去手动清零的麻烦，也避免了遗漏的风险。 - 如果非要用数组不可，记得在声明后立刻用
std::fill或memset进行初始化。 - 在处理每条边
u → v时，确保只执行一次inDegree[v]++，避免重复累加导致入度计算错误。
如何正确构建邻接表并遍历出边？注意 vector> 的索引方向
Kahn算法的核心逻辑是“从当前节点出发，能到达哪些节点”。因此，邻接表的构建方向至关重要：graph[u] 里存储的，必须是所有从节点 u 出发能直接到达的节点 v。如果方向搞反了，后续的BFS流程就无法正确更新下游节点的入度。
一个典型的错误是把边 u → v 存成了 graph[v].push_back(u)。这样一来，当BFS从队列中弹出节点 u 时，它试图去遍历 graph[u] 寻找出边，却发现里面是空的（或者根本不是它的后继节点），导致后续所有依赖它的节点入度都无法递减，全部被卡住。
- 在读入边的时候，明确地写成
graph[u].push_back(v)，并在心里默念“u指向v”。 - 一个简单的验证方法：打印出
graph[0]的内容，确认里面的元素确实都是从节点0出发能到达的终点。 - 特别注意：如果输入包含无向图的边，需要额外处理。拓扑排序只适用于有向无环图（DAG），无向边本身就构成了环，算法应该拒绝处理这种情况。
BFS过程中何时更新入度？必须在弹出节点后立即处理其所有邻接点
这里的逻辑顺序是关键。核心不是“遇到一个入度为0的节点就把它加入队列”，而是“每处理完一个节点，就把它所有后继节点的入度减1；减完之后，如果某个后继节点的入度变成了0，才把它加入队列”。如果这个顺序颠倒了（比如先入队再减），或者漏减了某个后继，整个拓扑序的生成就会被破坏。
从性能角度看，每次入度减1的操作是O(1)的，所以总的时间复杂度依然是O(V + E)。但如果你用了 map 或 set 来存储邻接关系，而没有预分配好空间，常数项可能会变大。在小规模数据上可能看不出来，但数据量一大，就有超时的风险。
- 标准的处理流程应该是：
int u = q.front(); q.pop();→ 遍历for (int v : graph[u])→inDegree[v]--;→ 检查if (inDegree[v] == 0)则q.push(v)。 - 不要在循环内部去修改
graph[u]这类容器（比如删除边），这既没必要，也容易引入错误。 - 使用普通的
queue就足够了，除非题目明确要求输出字典序最小的拓扑序，才需要考虑使用priority_queue。
怎么判断图含环？仅靠队列空还不够
这是Kahn算法一个非常优雅的特性：它天然具备环检测的能力。如果BFS结束后，队列空了，但得到的 result 序列长度小于节点总数 n，那就说明图中存在环。因为环内的所有节点，它们的入度永远无法被减到0，所以永远没有机会进入队列。
这里有个容易混淆的点：如果图是不连通的，但每个连通分量本身都是DAG（有向无环图），那么算法仍然可以完成排序。只有当图中存在至少一个有向环时，result 的长度才会“缩水”。另外，不要把孤立的节点（入度为0且出度也为0）误判为环的一部分——它们在算法一开始就会被加入队列。
- 所以，在算法最后，必须加上检查：
if (result.size() != n) { // 检测到环，进行相应处理 }。 - 不要试图用异常或者特殊的返回码来隐藏环的信息。在业务逻辑里，必须显式地处理存在环的这种情况。
- 调试时，可以额外统计“入队次数”和“出队次数”，理论上二者应该相等。如果不相等，那说明队列的弹出和压入逻辑可能有问题。
最后提一句，拓扑排序的结果本身通常不唯一。但是，基于入度统计和BFS的Kahn算法，只要输入和邻接表遍历顺序固定，每次运行得到的结果是稳定的。当然，如果你用了 unordered_set 这类无序容器来存储邻接关系，那输出的顺序就不可控了，这点需要注意。
IntelliJ IDEA 是 JetBrains 推出的专业集成开发环境，重点服务于 Java、Kotlin 与 JVM 项目开发。软件集成代码补全、静态检查、重构、调试、测试、版本控制及构建工具，并可借助插件扩展语言和框架支持。
JetBrains PyCharm 是面向 Python 开发者的集成开发环境，提供智能补全、代码检查、重构、调试、测试、版本控制及虚拟环境管理功能。Mac 版兼容 Intel 与 Apple 芯片，核心功能可免费使用。
JetBrains WebStorm 是面向 JavaScript、TypeScript 和现代 Web 技术的专业集成开发环境，可智能理解项目结构，提供代码补全、重构、错误检查、运行调试、测试及 Git 工具。
Adobe After Effects 是面向动态图形、影视特效与视频合成的专业创作软件。它提供关键帧动画、遮罩抠像、运动跟踪、三维空间、文字动画和表达式等工具，并可与 Premiere Pro、Photoshop、Illustrator
Adobe Audition 是面向播客、影视后期、音乐制作及内容创作者的专业音频工作站，提供波形精修、多轨录制与混音、频谱编辑、降噪修复、响度匹配和效果处理工具，并可与 Adobe Premiere 协同完成视频声音制作。
Adobe Bridge 是面向摄影师、设计师及内容团队的免费数字资产管理工具，可集中预览照片、视频和 Adobe 项目文件，并利用评级、标签、关键词、元数据、筛选与收藏集完成分类检索。它还支持批量重命名、格式导出、相机导入及 Camera
Adobe Illustrator 是 Adobe 推出的专业矢量图形设计软件，适合在 Mac 上制作标志、图标、插画、包装、信息图及印刷版面。它以路径和锚点构建可无损缩放的图形，并提供钢笔、形状、文字、图像描摹、渐变、画板及生成式功能。
Adobe InDesign 是面向印刷品与数字出版物的专业版面设计软件，可在 Mac 上制作书籍、杂志、宣传册、海报、报告及交互式文档。它提供精细的文字样式、网格、母版、长文档管理和印前输出能力。
Adobe Lightroom Classic 是面向桌面摄影工作流的照片管理与后期处理软件，可将原始照片保存在本地硬盘，通过目录、关键词、评分和收藏夹高效整理图库，并提供 RAW 冲印、蒙版、镜头校正、批量同步及多格式导出等功能。
Adobe Media Encoder 是 Adobe 推出的专业音视频编码与转码工具，可通过队列、预设和监视文件夹批量完成格式转换、代理文件创建及多平台成片输出，并与 Premiere Pro、After Effects 等软件紧密协作。
Adobe Photoshop 是面向摄影师、设计师和内容创作者的专业图像处理软件，提供图层、蒙版、选区、修复、调色、文字排版、智能对象及生成式编辑等能力。Mac 版支持 Intel 与 Apple Silicon 处理器。
Adobe Premiere Pro 是面向专业视频制作的非线性剪辑软件，提供多轨时间线、调色、音频处理、字幕、代理工作流和多格式输出能力，并可与 After Effects、Audition、Photoshop 及 Frame.io 协同
JetBrains IntelliJ IDEA 是以 Java、Kotlin 和 JVM 项目为核心的专业集成开发环境，提供智能补全、代码检查、安全重构、调试、测试、版本控制及构建工具集成。统一发行版的核心功能可免费用于商业和非商业项目，
PhpStorm 是 JetBrains 面向 PHP 与现代 Web 开发打造的专业集成开发环境，提供代码补全、静态检查、重构、调试、测试、数据库、版本控制及前端语言支持。Windows 用户可直接下载安装程序，
PyCharm 是 JetBrains 推出的 Python 集成开发环境，提供智能代码补全、错误检查、重构、调试、测试、Git、终端及 Jupyter Notebook 支持。统一版安装后可体验 30 天 Pro 功能，
WebStorm 是 JetBrains 面向 JavaScript、TypeScript 和现代 Web 技术打造的集成开发环境。它提供项目级代码分析、智能补全、安全重构、导航搜索，并集成调试、测试、终端、Git 与常用前端工具，
Adobe Photoshop 是面向摄影师、设计师和内容创作者的专业图像处理工具，可在 Windows 上完成照片修饰、选区抠图、图层合成、文字排版、绘画及生成式编辑。软件采用订阅授权，由 Creative Cloud 管理安装、更新与许
Adobe InDesign 是面向印刷与数字出版的专业页面排版工具，可制作书籍、杂志、宣传册、海报、交互式 PDF 和电子书。它提供精细的文字样式、多页面管理、印前检查及多格式输出能力，并能与 Photoshop、Illustrator
Adobe Illustrator 是用于绘制矢量图形、插画、图标、徽标和版式的专业设计工具。它以路径和锚点为核心，作品放大后仍能保持清晰，并提供画板、文字、渐变、图像描摹及精确变换等功能，适合品牌视觉、印刷物料、数字界面和商业插画创作。
Adobe Bridge 是 Adobe 推出的创意资产管理工具，可集中预览、分类和查找照片、视频、PDF及多种设计文件，并支持元数据、关键词、评级、批量重命名和格式导出。它可与 Photoshop、Illustrator 等应用衔接，
Adobe Lightroom Classic 是面向 Windows 桌面摄影工作流的照片管理与无损编辑工具，可通过目录集中整理大型图库，并完成 RAW 显影、局部蒙版、批量调整、打印和多格式导出。它强调本地文件管理与精细控制，
Adobe Acrobat Pro 是面向专业 PDF 工作的综合解决方案，可在 Windows 中创建、编辑、转换、比较、整理和保护文档，并支持表单、电子签名、扫描件文字识别及敏感信息永久遮盖。订阅还包含网页、移动服务和云端协作能力，
Adobe After Effects 是面向动态图形、动画与影视视觉特效制作的专业工具，可完成关键帧动画、图层合成、遮罩跟踪、抠像、文字动画和二维三维元素整合。Windows 版通过 Adobe Creative Cloud 安装及更新，
Adobe Media Encoder 是 Adobe 面向视频与音频制作流程提供的专业编码和转码工具，可批量处理媒体文件、创建代理、套用输出预设并监控文件夹自动执行任务。它与 Premiere、After Effects、Audition