資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用深度優先搜尋 (DFS) 查詢無向圖中所有連通分量的 Python 程式
當需要使用深度優先搜尋在無向圖中查詢所有連通分量時，定義一個包含初始化值、執行深度優先搜尋遍歷、查詢連通分量、向圖中新增節點等方法的類。可以建立類的例項，訪問其方法，並在其上執行操作。
下面是相同內容的演示 -
示例
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”的方法，該方法有助於確定相互連線的節點。
建立類的例項，並在其上呼叫方法。
節點顯示在控制檯上。
連通分量顯示為控制檯上的輸出。
更新於：2021年4月17日
1K+ 次瀏覽
廣告