เมื่อจำเป็นต้องค้นหาส่วนประกอบที่เชื่อมต่อทั้งหมดโดยใช้การค้นหาเชิงลึกก่อนในกราฟที่ไม่มีทิศทาง คลาสจะถูกกำหนดซึ่งประกอบด้วยวิธีการเริ่มต้นค่า ดำเนินการค้นหาในเชิงลึกก่อน ค้นหาส่วนประกอบที่เชื่อมต่อ เพิ่มโหนดในกราฟ และอื่นๆ สามารถสร้างอินสแตนซ์ของคลาสและเข้าถึงเมธอดและดำเนินการได้
ด้านล่างนี้เป็นการสาธิตสิ่งเดียวกัน -
ตัวอย่าง
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) ผลลัพธ์
1-->0 2-->3 3-->0 The connected components are : [[0, 1, 3, 2], [4]]
คำอธิบาย
-
มีการกำหนดคลาสชื่อ 'Graph_struct'
-
มีการกำหนดเมธอดชื่อ 'add_edge' ที่ช่วยเพิ่มองค์ประกอบให้กับทรี
-
มีการกำหนดวิธีการ 'DFS_Utility' ที่ช่วยสำรวจต้นไม้โดยใช้วิธีการค้นหาในเชิงลึกก่อน
-
มีการกำหนดเมธอดชื่อ 'connected_components' ที่ช่วยระบุโหนดที่เชื่อมต่อถึงกัน
-
มีการสร้างอินสแตนซ์ของคลาสและเรียกใช้เมธอด
-
โหนดจะแสดงบนคอนโซล
-
ส่วนประกอบที่เชื่อมต่อจะแสดงเป็นเอาต์พุตบนคอนโซล
