使用 BFS 查找无向图是否包含循环的 Python 程序

  • Z时代
  • 2024-01-10
  • 分类：综合

当需要求一棵树的所有节点的总和时，创建一个类，它包含设置根节点、向树添加元素、搜索特定元素以及将树的元素添加到的方法求总和等。可以创建类的实例来访问和使用这些方法。

以下是相同的演示 -

示例

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

以上是 使用 BFS 查找无向图是否包含循环的 Python 程序 的全部内容， 来源链接： utcz.com/z/317398.html

回到顶部