Circle Route Detection
系统讲述了图中的环路检测方法。
一般环路
在图论中，环路（或称回路、循环，英文为 "cycle"）是指在图中从某个顶点出发，沿着图的边经过一系列顶点，最后回到起始顶点的路径。环路的定义根据图的类型可以有所不同。
一般定义：
- 环路是一条路径，其中第一个节点与最后一个节点相同，并且路径中的每条边只走一次。更严格地说，环路是一个简单路径，即中间的顶点不重复。
无向图中的环路：
- 在无向图中，环路是一条从某个顶点出发，经过若干条边，最终回到该顶点的路径，并且路径中的顶点和边（除了起点和终点）不会重复。
- 无向图中的环路没有方向性。
有向图中的环路：
- 在有向图中，环路是指从某个顶点出发，沿着图的有向边，最终回到该顶点的路径，并且路径中的顶点和边（除了起点和终点）不会重复。
- 有向图中的环路要求边的方向一致，即必须遵循边的方向进行遍历。
特殊类型的环：
- 简单环路：如果环路除了起点和终点重合外，没有重复经过其他顶点或边，则称为简单环。
- 负权环：如果图中的边带有权值，并且一个环的边权值之和为负，则称为负权环。
- 自环：在有向图或无向图中，一个顶点指向自身的边，称为自环。自环是最简单的环。
- 欧拉环路：一条经过图中所有边且回到起始点的路径。
- 哈密顿环路：一条经过图中所有顶点且回到起始点的路径。
一般环路的检测
有向图
- 拓扑排序: 如果有向图不能产生对应的拓扑序列，则存在环。
无向图
- 并查集: 遍历每条边，合并边两侧的集合，如果两测的端点已经在同一集合内，则存在环。
DFS:- 从任意节点开始，进行
DFS遍历，如果有节点有邻居已经被访问过，并且该节点不是当前节点的父节点，那么存在环。 - 如果存在多个联通分量，在所有联通分量中执行上一步。
- 从任意节点开始，进行
负环
在图论中，负权回路（也称为负环）是指一个带权有向图中的回路，其边权值的总和小于零。换句话说，在这个回路中，从某个顶点出发，经过一系列边回到该顶点时，所经过的所有边的权值之和为负数。
负权回路在最短路径问题中非常重要，因为它表明可以通过反复循环回路来无限减小路径权值。在带有负权回路的图中，最短路径问题可能没有解决方案，因为路径的权值可以被无限次降低。
负环检测
检测的负环的一般思路是在距离更新中找到一条路径，这条路径中包含的节点数目大于图中的节点总数。需要强调的是，这条路径必须是一条距离更新(变小)的路径，因为一般朴素回路都会产生出大于节点总数的一般路径。而负权回路作为负权的发生源，会不断更新回路外节点的可达距离。这里的可达距离是抽象概念，并不相对于某个具体源点。
Bellman-Ford检测
- Bellman-Ford 章节中，已经阐释并且实现了这种方法。
Spfa检测
- 在spfa章节中，已经阐释并并且实现这中方法。
总结
可以总结出
- 一般环路的判断在路径转移过程中进行判断
- 负权环路的判断在距离更新的过程中进行判断
版权所有
版权归属：Pray0