DSA 图的循环检测
图中的循环
图中的循环是指一条路径，它从同一个顶点开始并结束于同一个顶点，其中不重复任何边。这就像在一个迷宫中行走，并最终回到了你开始的地方。
是否包含循环
循环的定义可能因情况而异。例如，一个自环，即一条边从同一个顶点出发并回到同一个顶点，可能被视为循环，也可能不被视为循环，这取决于您要解决的问题。
循环检测
能够检测图中的循环非常重要，因为在网络、调度和电路设计等许多应用中，循环可能表明存在问题或特殊情况。
最常见的两种检测循环的方法是：
- 深度优先搜索 (DFS)：DFS 遍历会探索图并标记已访问的顶点。当当前顶点有一个已经访问过的邻接顶点时，就会检测到循环。
- 并查集 (Union-Find)：该方法最初将每个顶点定义为一个组或一个子集。然后，对于每条边，将这些组连接起来。当探索一条新边时，如果两个顶点已经属于同一个组，则会检测到循环。
下面将更详细地解释 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 行：当调用 is_cyclic() 方法时，DFS 循环检测开始。
第 37 行：由于此时还没有访问任何顶点，因此 visited 数组首先被设置为所有顶点的 false。
第 38-42 行：对图中的所有顶点运行 DFS 循环检测。这是为了确保所有顶点都被访问到，以防图不连通。如果一个节点已经被访问过，则必然存在循环，并返回 True。如果所有节点只被访问一次，这意味着没有检测到循环，则返回 False。
第 24-34 行：这是 DFS 循环检测的一部分，它访问一个顶点，然后递归访问邻接顶点。如果一个邻接顶点已经被访问过，并且不是父节点，则检测到循环，并返回 True。
有向图的 DFS 循环检测
要检测有向图中的循环，算法仍然与无向图非常相似，但代码必须稍作修改，因为对于有向图，如果我们遇到一个已经被访问过的邻接节点，并不一定意味着存在循环。
考虑下面的图，其中探索了两个路径，试图检测循环：
在第一条路径（要探索的第一条路径）中，访问了顶点 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 方法合并子集。
