使用 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'方法被调用，输出显示在控制台上。