检测 图中的环

August 8, 2018 · View on GitHub

在图论中,一个图是一个边和顶点的路径,其中一个顶点可以自环路. 有几种不同类型的环路,主要是闭路和简单的环路.

定义

一个闭路由一个顶点的开始和结束 的顶点序列组成,在图中,序列中的每两个连续顶点彼此相邻. 在有向图中,

  • 遍历每个边必须与其方向一致地: 边必须从两个连续顶点中较早的一个定向到后一个.

  • 起始顶点的选择并不重要: 因为从不同的起始顶点遍历相同的边序列会产生相同的闭路.

一个简单环路可能

被定义为一个不允许重复顶点和边的闭路,除了重复起始和结束顶点,或者作为闭路的边集合.

  • 这两个定义在有向图中是等价的,其中简单环路也称为有向环路: 闭路中的顶点和边的环路序列完全由它使用的边集合确定.

  • 在无向图中,环路的边集合可以在两个方向中的任何一个方向上遍历,为每个无向环路提供两个可能的有向环路.

电路可以是闭路,允许重复顶点而不是边;但是,它也可以是一个简单的环路,因此在使用时,建议使用明确的定义.

例

Cycles

边颜色的图表说明路径 H-A-B (绿色) ,或闭路用重复的顶点走路 B-D-E-F-D-C-B (蓝色) 和环路没有重复的边的顶点H-D-G-H (红)

在无向图中环路

Undirected Cycle

在有向图中环路

Directed Cycle

参考

一般信息:

有向图中的环路: