Circle Route Detection

系统讲述了图中的环路检测方法。

一般环路

在图论中，环路（或称回路、循环，英文为 "cycle"）是指在图中从某个顶点出发，沿着图的边经过一系列顶点，最后回到起始顶点的路径。环路的定义根据图的类型可以有所不同。

一般定义：

• 环路是一条路径，其中第一个节点与最后一个节点相同，并且路径中的每条边只走一次。更严格地说，环路是一个简单路径，即中间的顶点不重复。

无向图中的环路：

• 在无向图中，环路是一条从某个顶点出发，经过若干条边，最终回到该顶点的路径，并且路径中的顶点和边（除了起点和终点）不会重复。
• 无向图中的环路没有方向性。

有向图中的环路：

• 在有向图中，环路是指从某个顶点出发，沿着图的有向边，最终回到该顶点的路径，并且路径中的顶点和边（除了起点和终点）不会重复。
• 有向图中的环路要求边的方向一致，即必须遵循边的方向进行遍历。

特殊类型的环：

• 简单环路：如果环路除了起点和终点重合外，没有重复经过其他顶点或边，则称为简单环。
• 负权环：如果图中的边带有权值，并且一个环的边权值之和为负，则称为负权环。
• 自环：在有向图或无向图中，一个顶点指向自身的边，称为自环。自环是最简单的环。
• 欧拉环路：一条经过图中所有边且回到起始点的路径。
• 哈密顿环路：一条经过图中所有顶点且回到起始点的路径。

一般环路的检测

有向图

• 拓扑排序: 如果有向图不能产生对应的拓扑序列，则存在环。

无向图

• 并查集: 遍历每条边，合并边两侧的集合，如果两测的端点已经在同一集合内，则存在环。
• DFS:
  • 从任意节点开始，进行DFS遍历，如果有节点有邻居已经被访问过，并且该节点不是当前节点的父节点，那么存在环。
  • 如果存在多个联通分量，在所有联通分量中执行上一步。

负环

在图论中，负权回路（也称为负环）是指一个带权有向图中的回路，其边权值的总和小于零。换句话说，在这个回路中，从某个顶点出发，经过一系列边回到该顶点时，所经过的所有边的权值之和为负数。

负权回路在最短路径问题中非常重要，因为它表明可以通过反复循环回路来无限减小路径权值。在带有负权回路的图中，最短路径问题可能没有解决方案，因为路径的权值可以被无限次降低。

负环检测

检测的负环的一般思路是在距离更新中找到一条路径，这条路径中包含的节点数目大于图中的节点总数。需要强调的是，这条路径必须是一条距离更新(变小)的路径，因为一般朴素回路都会产生出大于节点总数的一般路径。而负权回路作为负权的发生源，会不断更新回路外节点的可达距离。这里的可达距离是抽象概念，并不相对于某个具体源点。

Bellman-Ford 检测

• Bellman-Ford 章节中，已经阐释并且实现了这种方法。

Spfa 检测

• 在spfa章节中，已经阐释并并且实现这中方法。

总结

可以总结出

• 一般环路的判断在路径转移过程中进行判断
• 负权环路的判断在距离更新的过程中进行判断