检测图中的循环
大约 2 分钟
检测图中的循环
在图论中，循环是指一条由边和顶点组成的路径，其中一个顶点可以从自身到达。循环有几种不同的类型，主要有闭合路径和简单循环。
定义
闭合路径由一系列从同一顶点开始和结束的顶点组成，序列中的任意两个连续顶点在图中相邻。在有向图中，每条边在路径中的遍历必须与其方向一致：边必须从序列中较早的顶点指向序列中较后的顶点。起始顶点的选择并不重要：从不同的起始顶点遍历相同的循环边序列会产生相同的闭合路径。
简单循环可以定义为一条闭合路径，不允许重复顶点和边，除了起始和结束顶点的重复，或者可以定义为该路径中的边的集合。在有向图中，这两种定义是等价的，简单循环也被称为有向循环：在循环中的顶点和边的循环序列完全由其使用的边的集合确定。在无向图中，循环的边集可以按照两个方向之一遍历，为每个无向循环提供两种可能的有向循环。电路可以是允许重复顶点但不允许重复边的闭合路径；然而，它也可以是简单循环，因此在使用时建议明确定义。
示例
带有颜色边的图，用于说明路径 H-A-B（绿色），带有重复顶点的闭合路径或循环路径 B-D-E-F-D-C-B（蓝色）以及没有重复边或顶点的循环 H-D-G-H（红色）
无向图中的循环
有向图中的循环
参考资料
常规信息：
无向图中的循环：
有向图中的循环：
