DSA 图的循环检测
图中的循环
图中的循环是指一条从某个顶点开始并以相同顶点结束的路径，路径上没有重复的边。这就像在一个迷宫中行走，最终回到起点。
是否循环
根据情况，循环的定义可能略有不同。例如，自环（一条边从同一个顶点开始并结束），根据你试图解决的问题，可能被认为是循环，也可能不被认为是循环。
循环检测
能够检测图中的循环非常重要，因为循环在许多应用中，如网络、调度和电路设计，可能表明问题或特殊情况。
检测循环最常用的两种方法是
- 深度优先搜索 (DFS): DFS 遍历会探索图并标记顶点为已访问。当当前顶点有一个相邻顶点已被访问时，就会检测到循环。
- 并查集: 该方法最初将每个顶点定义为一个组或子集。然后，对于每条边，这些组都会被合并。当探索一条新边时，如果两个顶点已属于同一个组，则表示已检测到循环。
下面将详细解释 DFS 和并查集如何进行循环检测以及它们的实现方式。
无向图的 DFS 循环检测
为了使用深度优先搜索 (DFS) 检测无向图中的循环，我们使用与上一页的 DFS 遍历代码非常类似的代码，只做了一些修改。
工作原理
- 从每个未访问的顶点开始 DFS 遍历（如果图不是连通的）。
- 在 DFS 过程中，标记顶点为已访问，并在相邻顶点上运行 DFS（递归）。
- 如果一个相邻顶点已被访问且不是当前顶点的父节点，则表示检测到循环，并返回
True。 - 如果所有顶点都完成了 DFS 遍历且没有检测到循环，则返回
False。
运行下面的动画，观察 DFS 循环检测如何在特定的图上运行，从顶点 A 开始（这与上一个动画相同）。
是否循环
DFS 遍历从顶点 A 开始，因为它是邻接矩阵中的第一个顶点。然后，对于每个新访问的顶点，遍历方法会在所有尚未访问的相邻顶点上递归调用。当访问顶点 F 时，检测到循环，并发现相邻顶点 C 已经访问过。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited, parent):
visited[v] = True
for i in range(self.size):
if self.adj_matrix[v][i] == 1:
if not visited[i]:
if self.dfs_util(i, visited, v):
return True
elif parent != i:
return True
return False
def is_cyclic(self):
visited = [False] * self.size
for i in range(self.size):
if not visited[i]:
if self.dfs_util(i, visited, -1):
return True
return False
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D - A
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(0, 4) # A - E
g.add_edge(4, 2) # E - C
g.add_edge(2, 5) # C - F
g.add_edge(2, 1) # C - B
g.add_edge(2, 6) # C - G
g.add_edge(1, 5) # B - F
g.print_graph()
print("\nGraph has cycle:", g.is_cyclic())
第 66 行: DFS 循环检测在调用 is_cyclic() 方法时开始。
第 37 行: visited 数组最初被设置为所有顶点的 false，因为此时还没有访问任何顶点。
第 38-42 行: 在图中的所有顶点上运行 DFS 循环检测。这样做是为了确保所有顶点都被访问，以防图不是连通的。如果某个节点已被访问，则表示一定存在循环，并返回 True。如果所有节点都只访问一次，这意味着没有检测到循环，则返回 False。
第 24-34 行: 这是 DFS 循环检测的一部分，它会访问某个顶点，然后递归访问相邻顶点。如果某个相邻顶点已被访问，且不是父节点，则表示检测到循环，并返回 True。
有向图的 DFS 循环检测
为了检测有向图中的循环，该算法仍然与无向图非常相似，但代码需要进行一些修改，因为对于有向图，如果我们到达一个已被访问的相邻节点，并不一定意味着存在循环。
请考虑下面的图，其中探索了两条路径，试图检测循环
在路径 1 中，第一个要探索的路径，访问了顶点 A->B->C，没有检测到循环。
在第二个要探索的路径（路径 2）中，访问了顶点 D->B->C，路径中没有循环，对吧？但是，如果没有对我们的程序进行更改，当从 D 到相邻顶点 B 时，实际上会检测到一个错误的循环，因为 B 在路径 1 中已被访问。为了避免这种错误的检测，代码被修改为只在某个节点之前在同一条路径中被访问时才检测循环。
是否循环
为了在有向图上实现 DFS 循环检测，就像上面的动画一样，我们需要删除无向图的邻接矩阵中的对称性。我们还需要使用 recStack 数组来跟踪当前递归路径中访问的顶点。
示例
Python
class Graph:
# ......
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
# ......
def dfs_util(self, v, visited, recStack):
visited[v] = True
recStack[v] = True
print("Current vertex:",self.vertex_data[v])
for i in range(self.size):
if self.adj_matrix[v][i] == 1:
if not visited[i]:
if self.dfs_util(i, visited, recStack):
return True
elif recStack[i]:
return True
recStack[v] = False
return False
def is_cyclic(self):
visited = [False] * self.size
recStack = [False] * self.size
for i in range(self.size):
if not visited[i]:
print() #new line
if self.dfs_util(i, visited, recStack):
return True
return False
g = Graph(7)
# ......
g.add_edge(3, 0) # D -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 1) # C -> B
g.add_edge(2, 4) # C -> E
g.add_edge(1, 5) # B -> F
g.add_edge(4, 0) # E -> A
g.add_edge(2, 6) # C -> G
g.print_graph()
print("Graph has cycle:", g.is_cyclic())
第 6 行: 删除了这一行，因为它只适用于无向图。
第 26 行: recStack 数组保存了对在递归探索路径期间访问的顶点的概述。
第 14-19 行: 对于每个之前未访问的相邻顶点，执行递归 DFS 循环检测。如果某个相邻顶点之前已被访问，并且也在同一个递归路径中（第 13 行），则表示已找到循环，并返回 True。
并查集循环检测
使用并查集检测循环与使用深度优先搜索截然不同。
并查集循环检测的工作原理是，首先将每个节点放入它自己的子集中（就像一个袋子或容器）。然后，对于每条边，合并属于每个顶点的子集。对于一条边，如果两个顶点已属于同一个子集，则表示我们找到了一个循环。
是否循环
在上面的动画中，并查集循环检测探索了图中的边。当探索边时，顶点 A 的子集会扩展到也包含顶点 B、C 和 D。当探索 A 和 D 之间的边时，检测到循环，并且发现 A 和 D 已属于同一个子集。
D、E 和 F 之间的边也构成了一个圆圈，但这个圆圈没有被检测到，因为算法在检测到第一个圆圈时停止（返回 True）。
并查集循环检测只适用于无向图。
并查集循环检测是使用邻接矩阵表示来实现的，因此使用顶点和边设置图结构基本上与之前的例子相同。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
self.parent = [i for i in range(size)] # Union-Find array
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def find(self, i):
if self.parent[i] == i:
return i
return self.find(self.parent[i])
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
print('Union:',self.vertex_data[x],'+',self.vertex_data[y])
self.parent[x_root] = y_root
print(self.parent,'\n')
def is_cyclic(self):
for i in range(self.size):
for j in range(i + 1, self.size):
if self.adj_matrix[i][j]:
x = self.find(i)
y = self.find(j)
if x == y:
return True
self.union(x, y)
return False
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(1, 0) # B - A
g.add_edge(0, 3) # A - D
g.add_edge(0, 2) # A - C
g.add_edge(2, 3) # C - D
g.add_edge(3, 4) # D - E
g.add_edge(3, 5) # D - F
g.add_edge(3, 6) # D - G
g.add_edge(4, 5) # E - F
print("Graph has cycle:", g.is_cyclic())
第 6 行: parent 数组包含每个子集的根顶点。这用于通过检查一条边两端的两个顶点是否已属于同一个子集来检测循环。
第 17 行: find 方法找到给定顶点所属的集合的根。
第 22 行: union 方法合并两个子集。
第 29 行: is_cyclic 方法使用 find 方法来检测循环，如果两个顶点 x 和 y 已在同一个子集中。如果没有检测到循环，则使用 union 方法合并子集。
