数据结构
网络
关系数据库管理系统(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 次浏览
广告