Cosmos 中基于节点度数（Degree of Nodes）检测无向图环的 C++ 实现指南

Cosmos 中基于节点度数Degree of Nodes检测无向图环的 C 实现指南【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos无向图中的环检测是图论中的基础问题除常规的 DFS、并查集方法外还有一条直观且巧妙的路径反复剥离度为 1的悬挂节点若最后仍留有未被剥离的节点则它们必然构成一个或多个环。本文以 code/languages/cpp/detect_cycle_undirected_graph_using_degrees_of_nodes 目录下的 README 与源码为主体完整讲解该方法的核心原理、C 实现、复杂度分析并结合仓库中其他环检测实现DFS、并查集、BFS进行横向对比。读完本文你将掌握一种不依赖递归栈、却能同时定位出环上全部节点的检测方案并能够独立编译运行示例代码。1. 方法概述为什么度数为 1 的节点不可能是环的一部分在一个无向图中环Cycle是一条首尾相接且不重复经过节点的闭合路径。观察环的结构可以发现一个关键性质环上的每个节点至少有 2 条边一条进、一条出即度数 ≥ 2度为 0 的节点是孤立点度为 1 的节点是悬挂节点leaf它们都不可能出现在任何环上。因此一个朴素而有效的思路是反复删除所有度数为 1 的节点。删除一个悬挂节点后它的唯一邻居度数会减 1可能降级为新的悬挂节点于是继续剥离。这个过程可以形象地理解为剥洋葱——把图中所有非环部分一层层削掉。当无法再找到度数为 1 的节点时若所有节点都已被剥离则图中不存在环若仍有节点剩余则剩余节点全部属于某个环或若干环。该 README 明确声明了这一方法的目标An intuitive and simple approach to detect cycle and print the nodes forming the cycle in the graph即不仅能判定是否存在环还能打印出构成环的节点集合这是它与仅返回布尔值的 DFS 方案如 cycle_undirected_graph.cpp最大的不同。方法用到的三种核心数据结构原 README 强调本实现只依赖三种数据结构数据结构用途对应源码detect_cycle_graph_using_degree.cppMap邻接表存储无向图的邻接关系mapint, vectorint adjList;第 12 行Queue存放所有度为 1 的节点等待被剥离queueint q;第 51 行Boolean Array标记节点是否已被访问已剥离bool visited[n];第 48 行从源码结构看实现还额外引入了一个unordered_mapint, int deg来动态维护每个节点的当前度数这是在剥离过程中反复更新度数所必需的。2. 算法执行流程与 C 源码逐段剖析整体流程可分为三个阶段图的输入与邻接表构建、循环剥离度为 1 的节点、输出环检测结果。2.1 输入阶段构建无向图邻接表源码中graph::input()第 19–41 行负责读取顶点数n、边数e并对每条无向边同时写入两个方向的邻接关系for (int i 0; i e; i) { int start, end; cin start; cin end; adjList[start].push_back(end); adjList[end].push_back(start); }注意无向图的对称性(start, end)与(end, start)两条记录都必须存在否则度数计算会出错。输入完成后程序会原样打印邻接表方便核对数据。2.2 核心循环反复剥离度为 1 的节点graph::detect_cycle()第 43–87 行先统计每个节点的初始度数unordered_mapint, int deg; for (int i 0; i n; i) { deg[i] adjList[i].size(); }随后进入外层while (1)循环第 52–71 行每一轮执行两步操作扫描并入队遍历deg把所有当前度数为 1 且尚未访问的节点压入队列q批量剥离逐个弹出队列节点将其标记为visited true并遍历其邻接表将每个邻居的度数减 1deg[adjList[temp][i]]--。当队列为空即不再有度数为 1 的节点时外层循环终止。代码中的注释 recursively updating the nodes with degree 1 点明了这一机制的实质剥除一个悬挂节点会让其邻居度数下降从而可能在下一轮产生新的悬挂节点如此迭代直至稳定。2.3 输出阶段判定并打印环上节点剥离结束后扫描所有顶点的visited标志第 72–86 行int f 0; for (int i 0; i n; i) { if (visited[i] false) f 1; } if (f 0) cout No cycle detected !\n; else { cout Cycle detected \n; for (int i 0; i n; i) { if (visited[i] false) cout i ; } }若全部顶点都已被访问说明图是森林无环否则所有未被访问的顶点就是环上或环集合中的节点程序将它们逐一打印。2.4 编译与运行该实现只依赖标准库头文件map、queue、unordered_map、vector、iostream、cstdlib任何支持 C11 的编译器均可直接编译例如g -stdc11 -O2 detect_cycle_graph_using_degree.cpp -o detect_cycle ./detect_cycle2.5 示例输入演示以顶点数n 5、边数e 5的一个含环图为例输入5 5 0 1 1 2 2 0 2 3 3 4程序会先打印邻接表再输出Cycle detected 0 1 2节点 0、1、2 恰好构成三角形环而悬挂链2–3–4上的节点 3、4 已被依次剥离3 度数为 1 被剥后4 降为度数 1 再被剥。再以无环图如n 3、边0 1、1 2为例输出为No cycle detected !。3. 复杂度分析设顶点数为 V、边数为 E时间复杂度每一轮外层循环都要完整扫描deg找出度数为 1 的节点最坏情况下每轮只剥离一个节点需要 O(V) 轮每轮扫描 O(V) 并更新 O(E) 次度数整体可视为 O(V² E·V) 级别的量级相比 DFS/并查集方案的 O(V E)该实现以更多时间为代价换来了直接定位环上节点的能力。空间复杂度需要存储邻接表 O(V E)、度数表 O(V)、队列与 visited 数组 O(V)总计 O(V E)。需要说明的是原 README 未给出复杂度结论以上量级是根据源码结构每轮全量扫描deg可以推断出的上界分析。对于竞赛或大规模图cycle_undirected_graph.cpp 的 DFS 方案或并查集方案通常更快。4. 仓库内同类问题实现对比DFS、并查集与 BFSCosmos 仓库在 code/graph_algorithms/src/cycle_undirected_graph/ 目录下还提供了多种无向图环检测实现可与本方法对照学习方案代表文件核心思想是否能打印环上节点度数剥离本文detect_cycle_graph_using_degree.cpp反复移除度为 1 的节点能DFS 父节点cycle_undirected_graph.cpp遍历时若遇到已访问且非父节点的邻居则成环否仅布尔判定并查集Union-Findcycle_undirected_graph_union_find.cpp逐边合并集合若边的两端已属同一集合则成环带路径压缩与按秩合并优化否BFS 分层着色cycle_undirected_graph.py以 layer 分层遇到层号不小于当前节点的邻居即判环否其中并查集实现cycle_undirected_graph_union_find.cpp通过findset的路径压缩与unionset的按秩合并能在近似 O(E·α(V)) 的时间完成检测是工程上常用且高效的选择。此外若需要检测有向图中的环仓库提供了基于 DFS 递归栈recursion stack的 cycle_directed_graph.cpp其核心在于用一个额外的recStack数组判断节点是否在当前 DFS 路径上而不是仅仅是否被访问过——这正是有向图与无向图环检测的本质区别。相关实现还有 cycle_directed_graph.py 与 C 语言版本。5. 适用场景、局限与优化方向适用场景需要同时回答是否存在环与哪些节点在环上两类问题图中存在大量悬挂分支度数剥离法能快速修剪掉无关部分教学演示该实现结构清晰与 DFS 的递归思维形成互补。局限性每轮全量扫描度数表导致最坏时间复杂度较高对稠密图或超大图效率不佳此时应优先考虑 DFS 或并查集方案原实现的visited使用 VLA变长数组bool visited[n]严格来说依赖编译器扩展更稳妥的写法是使用vectorbool或std::vectorchar输入假设顶点编号连续为 0..n-1且节点必须显式出现在邻接表中才能被正确统计度数从源码第 45–47 行可以看出deg[i] adjList[i].size()直接对 0 到 n-1 的每个编号取邻接表长度。优化方向可以用一个初始队列装好所有度数为 1 的节点弹出时再动态判断邻居是否降为度数 1 并立即入队从而将单轮全量扫描变为增量更新把复杂度优化到接近 O(V E)这也是拓扑排序思想的直接应用。仓库中的 拓扑排序实现 与其在数据结构上有相通之处可作延伸阅读。6. 总结基于节点度数的环检测方法用度为 1 的节点不可能成环这一简单观察把环检测问题转化为反复剥离悬挂节点的迭代过程并且天然具备输出环上节点集合的能力。本文结合 detect_cycle_graph_using_degree.cpp 的完整源码逐段讲解了 Map、Queue、Boolean Array 三种数据结构的配合方式给出了可复现的编译命令与输入输出示例并与仓库中 DFS、并查集、BFS 三种同类实现做了对比。理解这一方法后你既能在合适的场景下直接使用它也能将剥洋葱的思想迁移到拓扑排序、K 核分解等其他图算法问题中。【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考