Phát hiện chu kỳ đồ thị DSA
Chu kỳ trong đồ thị
Một chu trình trong Đồ thị là một đường đi bắt đầu và kết thúc ở cùng một đỉnh, trong đó không có cạnh nào được lặp lại. Nó giống như việc bạn đi qua một mê cung và kết thúc ở đúng nơi bạn đã bắt đầu.
Có tính tuần hoàn:
Một chu kỳ có thể được định nghĩa hơi khác nhau tùy theo tình huống. Ví dụ: một vòng lặp tự, trong đó một cạnh đi từ và đến cùng một đỉnh, có thể được coi là một chu trình hoặc không, tùy thuộc vào vấn đề bạn đang cố gắng giải quyết.
Phát hiện chu kỳ
Điều quan trọng là có thể phát hiện các chu trình trong Biểu đồ vì các chu trình có thể chỉ ra sự cố hoặc điều kiện đặc biệt trong nhiều ứng dụng như kết nối mạng, lập lịch và thiết kế mạch.
Hai cách phổ biến nhất để phát hiện chu kỳ là:
- Tìm kiếm theo chiều sâu (DFS): Truyền tải DFS khám phá Biểu đồ và đánh dấu các đỉnh là đã truy cập. Một chu trình được phát hiện khi đỉnh hiện tại có một đỉnh liền kề đã được ghé thăm.
- Union-Find: Tính năng này hoạt động bằng cách ban đầu xác định mỗi đỉnh là một nhóm hoặc một tập hợp con. Sau đó, các nhóm này được nối với nhau ở mọi cạnh. Bất cứ khi nào một cạnh mới được khám phá, một chu trình sẽ được phát hiện nếu hai đỉnh đã thuộc cùng một nhóm.
Cách phát hiện chu trình bằng DFS và Union-Find hoạt động cũng như cách triển khai chúng được giải thích chi tiết hơn bên dưới.
Phát hiện chu trình DFS cho đồ thị vô hướng
Để phát hiện các chu trình trong Đồ thị vô hướng bằng cách sử dụng Tìm kiếm theo chiều sâu (DFS), chúng tôi sử dụng một mã rất giống với mã truyền tải DFS trên trang trước, chỉ với một vài thay đổi.
Làm thế nào nó hoạt động:
- Bắt đầu truyền tải DFS trên mỗi đỉnh chưa được thăm (trong trường hợp Đồ thị không được kết nối).
- Trong DFS, đánh dấu các đỉnh là đã truy cập và chạy DFS trên các đỉnh liền kề (đệ quy).
- Nếu một đỉnh liền kề đã được truy cập và không phải là đỉnh cha của đỉnh hiện tại thì một chu trình sẽ được phát hiện và trả về
True. - Nếu quá trình truyền tải DFS được thực hiện trên tất cả các đỉnh và không phát hiện thấy chu kỳ nào, thì trả về
False.
Chạy hoạt ảnh bên dưới để xem cách phát hiện chu trình DFS chạy trên một Biểu đồ cụ thể, bắt đầu từ đỉnh A (điều này giống với hoạt ảnh trước đó).
Có tính tuần hoàn:
Quá trình truyền tải DFS bắt đầu ở đỉnh A vì đó là đỉnh đầu tiên trong ma trận kề. Sau đó, với mỗi đỉnh mới được thăm, phương pháp truyền tải được gọi đệ quy trên tất cả các đỉnh liền kề chưa được thăm. Chu trình được phát hiện khi đỉnh F được thăm và người ta phát hiện ra rằng đỉnh C liền kề đã được thăm.
Ví dụ
Trăn:
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())
Chạy ví dụ » Dòng 66: Quá trình phát hiện chu trình DFS bắt đầu khi phương thức is_cyclic() được gọi.
Dòng 37: Mảng visited trước tiên được đặt thành false cho tất cả các đỉnh, vì chưa có đỉnh nào được truy cập tại thời điểm này.
Dòng 38-42: Phát hiện chu trình DFS được chạy trên tất cả các đỉnh trong Biểu đồ. Điều này nhằm đảm bảo tất cả các đỉnh đều được truy cập trong trường hợp Biểu đồ không được kết nối. Nếu một nút đã được truy cập thì phải có một chu trình và trả về True . Nếu tất cả các nút chỉ được truy cập, nghĩa là không phát hiện thấy chu kỳ nào, thì trả về False .
Dòng 24-34: Đây là một phần của quá trình phát hiện chu trình DFS truy cập một đỉnh và sau đó truy cập các đỉnh liền kề theo cách đệ quy. Một chu trình được phát hiện và True được trả về nếu một đỉnh liền kề đã được truy cập và nó không phải là nút cha.
Phát hiện chu trình DFS cho đồ thị có hướng
Để phát hiện các chu trình trong Đồ thị có hướng, thuật toán vẫn rất giống với Đồ thị vô hướng, nhưng mã phải được sửa đổi một chút vì đối với Đồ thị có hướng, nếu chúng ta đến một nút liền kề đã được truy cập thì nó sẽ làm như vậy. không nhất thiết có nghĩa là có một chu kỳ.
Chỉ cần xem xét Biểu đồ sau trong đó hai đường dẫn được khám phá, cố gắng phát hiện một chu trình:
Trong đường dẫn 1, đường dẫn đầu tiên được khám phá, các đỉnh A->B->C được thăm, không phát hiện thấy chu trình nào.
Trong đường đi thứ hai cần khám phá (đường dẫn 2), các đỉnh D->B->C đã được thăm và đường đi không có chu trình, phải không? Nhưng nếu không có những thay đổi trong chương trình của chúng ta, một chu trình sai sẽ thực sự được phát hiện khi đi từ D đến đỉnh B liền kề, bởi vì B đã được truy cập ở đường dẫn 1. Để tránh những phát hiện sai như vậy, mã được sửa đổi để chỉ phát hiện các chu trình trong trường hợp một nút đã được truy cập trước đó trên cùng một đường dẫn.
Có tính tuần hoàn:
Để triển khai phát hiện chu trình DFS trên Đồ thị có hướng, như trong hoạt ảnh ở trên, chúng ta cần loại bỏ tính đối xứng mà chúng ta có trong ma trận kề cho Đồ thị vô hướng. Chúng ta cũng cần sử dụng mảng recStack để theo dõi các đỉnh đã truy cập trong đường dẫn đệ quy hiện tại.
Ví dụ
Trăn:
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())
Chạy ví dụ »Dòng 6: Dòng này bị lược bỏ vì chỉ áp dụng cho đồ thị vô hướng.
Dòng 26: Mảng recStack giữ một cái nhìn tổng quan về các đỉnh đã được truy cập trong quá trình khám phá đệ quy một đường dẫn.
Dòng 14-19: Đối với mọi đỉnh liền kề chưa được ghé thăm trước đó, hãy thực hiện phát hiện chu trình DFS đệ quy. Nếu một đỉnh liền kề đã được truy cập trước đó, cũng trong cùng một đường đệ quy (dòng 13), thì một chu trình đã được tìm thấy và trả về True .
Phát hiện chu trình tìm kiếm liên minh
Việc phát hiện chu trình bằng Union-Find rất khác với việc sử dụng Tìm kiếm theo chiều sâu.
Tính năng phát hiện chu trình Union-Find hoạt động bằng cách trước tiên đặt mỗi nút vào tập hợp con của chính nó (như túi hoặc hộp đựng). Sau đó, với mỗi cạnh, các tập con thuộc mỗi đỉnh được hợp nhất. Đối với một cạnh, nếu các đỉnh đã thuộc cùng một tập con thì có nghĩa là chúng ta đã tìm được một chu trình.
Có tính tuần hoàn:
Trong hoạt ảnh ở trên, tính năng phát hiện chu trình Union-Find khám phá các cạnh trong Biểu đồ. Khi các cạnh được khám phá, tập hợp con của đỉnh A phát triển để bao gồm cả các đỉnh B, C và D. Chu trình được phát hiện khi cạnh giữa A và D được khám phá và người ta phát hiện ra rằng cả A và D đều thuộc về cùng một tập hợp con.
Các cạnh giữa D, E và F cũng tạo thành một đường tròn, nhưng đường tròn này không được phát hiện vì thuật toán dừng (trả về True ) khi phát hiện đường tròn đầu tiên.
Tính năng phát hiện chu trình Union-Find chỉ áp dụng cho các Đồ thị vô hướng.
Việc phát hiện chu trình Union-Find được triển khai bằng cách sử dụng biểu diễn ma trận kề , do đó việc thiết lập cấu trúc Đồ thị với các đỉnh và cạnh về cơ bản giống như trong các ví dụ trước.
Ví dụ
Trăn:
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())
Chạy ví dụ » Dòng 6: Mảng parent chứa đỉnh gốc của mọi tập hợp con. Điều này được sử dụng để phát hiện một chu trình bằng cách kiểm tra xem hai đỉnh ở hai bên của một cạnh đã thuộc cùng một tập hợp con hay chưa.
Dòng 17: Phương thức find tìm nghiệm của tập hợp chứa đỉnh đã cho.
Dòng 22: Phương thức union kết hợp hai tập hợp con.
Dòng 29: Phương thức is_cyclic sử dụng phương thức find để phát hiện một chu trình nếu hai đỉnh x và y đã nằm trong cùng một tập hợp con. Nếu không phát hiện được chu trình, phương pháp union sẽ được sử dụng để kết hợp các tập hợp con.
