資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用BFS查詢無向圖中是否存在環的Python程式
當需要查詢樹中所有節點的總和時，建立一個類，其中包含設定根節點、向樹中新增元素、搜尋特定元素以及新增樹的元素以查詢總和等方法。可以建立類的例項來訪問和使用這些方法。
以下是相同的演示 -
示例
from collections import deque
def add_edge(adj: list, u, v):
adj[u].append(v)
adj[v].append(u)
def detect_cycle(adj: list, s, V, visited: list):
parent = [-1] * V
q = deque()
visited[s] = True
q.append(s)
while q != []:
u = q.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)
parent[v] = u
elif parent[u] != v:
return True
return False
def cycle_disconnected(adj: list, V):
visited = [False] * V
for i in range(V):
if not visited[i] and detect_cycle(adj, i, V, visited):
return True
return False
if __name__ == "__main__":
V = 5
adj = [[] for i in range(V)]
add_edge(adj, 0, 1)
add_edge(adj, 1, 2)
add_edge(adj, 2, 0)
add_edge(adj, 2, 3)
add_edge(adj, 2, 1)
if cycle_disconnected(adj, V):
print("There are 5 vertices in the graph")
print("0-->1")
print("1-->2")
print("2-->0")
print("2-->3")
print("2-->1")
print("Is there a cycle ?")
print("Yes")
else:
print("There are 5 vertices in the graph")
print("0-->1")
print("1-->2")
print("2-->0")
print("2-->3")
print("2-->1")
print("Is there a cycle ?")
print("Yes")
print("No")輸出
There are 5 vertices in the graph 0-->1 1-->2 2-->0 2-->3 2-->1 Is there a cycle ? Yes
解釋
匯入所需的包。
定義另一個名為“add_edge”的方法，該方法有助於向圖中新增節點。
定義一個名為“detect_cycle”的方法，該方法有助於確定連線圖的元件時是否形成環。
定義另一個名為“cycle_disconnected”的方法，該方法有助於確定迴圈是連線的還是非連線的。
使用“add_edge”方法將元素新增到圖中。
它顯示在控制檯上。
呼叫“cycle_disconnected”方法並在控制檯上顯示輸出。
更新於：2021年4月17日
354 次瀏覽
廣告