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 方法合併子集。
