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

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

下面是相同的演示−

更多Python相关文章，请阅读：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("有5个顶点在图中")
        print("0-->1")
        print("1-->2")
        print("2-->0")
        print("2-->3")
        print("2-->1")
        print("是否有一个循环?")
        print("Yes")
    else:
        print("有5个顶点在图中")
        print("0-->1")
        print("1-->2")
        print("2-->0")
        print("2-->3")
        print("2-->1")
        print("是否有一个循环?")
        print("Yes")
        print("没有")

输出

有5个顶点在图中
0-->1
1-->2
2-->0
2-->3
2-->1
是否有一个循环?
Yes

解释

• 导入所需的模块

• 定义一个名为“add_edge”的方法，该方法有助于向图中添加节点

• 定义一个名为“detect_cycle”的方法，该方法有助于确定在连接图的组件时是否形成循环。

• 定义一个名为“cycle_disconnected”的方法，该方法有助于确定循环是否连接

• 使用“add_edge”方法添加元素到图中

• 在控制台上显示结果

• 调用“cycle_disconnected”方法并在控制台上显示结果