Khi được yêu cầu tìm tất cả các thành phần được kết nối bằng cách sử dụng tìm kiếm độ sâu đầu tiên trong một biểu đồ vô hướng, một lớp được xác định chứa các phương thức để khởi tạo giá trị, thực hiện truyền tải tìm kiếm độ sâu đầu tiên, tìm các thành phần được kết nối, thêm các nút vào biểu đồ, v.v. Phiên bản của lớp có thể được tạo và các phương thức có thể được truy cập và các hoạt động cũng như được thực hiện trên nó.
Dưới đây là một minh chứng về điều tương tự -
Ví dụ
class Graph_struct:
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
def DFS_Utililty(self, temp, v, visited):
visited[v] = True
temp.append(v)
for i in self.adj[v]:
if visited[i] == False:
temp = self.DFS_Utililty(temp, i, visited)
return temp
def add_edge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
def connected_components(self):
visited = []
conn_compnent = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
conn_compnent.append(self.DFS_Utililty(temp, v, visited))
return conn_compnent
my_instance = Graph_struct(5)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 0)
print("1-->0")
print("2-->3")
print("3-->0")
conn_comp = my_instance.connected_components()
print("The connected components are :")
print(conn_comp) Đầu ra
1-->0 2-->3 3-->0 The connected components are : [[0, 1, 3, 2], [4]]
Giải thích
-
Một lớp có tên ‘Graph_struct’ được xác định.
-
Một phương thức có tên là ‘add_edge’ được định nghĩa để giúp thêm các phần tử vào cây.
-
Phương thức ‘DFS_Utility’ được định nghĩa để giúp xem qua cây bằng cách sử dụng phương pháp tìm kiếm theo độ sâu đầu tiên.
-
Một phương thức có tên là ‘connect_components’ được xác định, giúp xác định các nút được kết nối với nhau.
-
Một thể hiện của lớp được tạo và các phương thức được gọi trên đó.
-
Nút được hiển thị trên bảng điều khiển.
-
Các thành phần được kết nối được hiển thị dưới dạng đầu ra trên bảng điều khiển.