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

在计算机科学中，图是由节点（或顶点）和边组成的数据结构。无向图是一种边没有方向的图，顾名思义，其边是没有定向的。循环（或环路）是图中至少有一个节点能够被访问两次的一条路径。查找无向图中是否存在循环或环路，是图论中一个非常基本的问题。

广度优先搜索（BFS）是一种遍历或搜索图的算法，从一个顶点出发，按照距离顺序遍历与该顶点相邻的点。本文将演示如何使用BFS查找无向图是否包含循环或环路的程序。

更多Python相关文章，请阅读：Python 教程

代码实现

首先需要定义图节点的数据结构，我们需要一个列表将每个节点的邻居存储在一起：

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

接着，我们需要实现BFS算法：

def bfs(graph, node):
    queue = [(node, None)]
    visited = set()
    while queue:
        curr, parent = queue.pop(0)
        if curr in visited:
            return True
        visited.add(curr)
        for neighbor in curr.neighbors:
            if neighbor != parent:
                queue.append((neighbor, curr))
    return False

上述代码中，bfs 函数接受两个参数： graph 和起始节点 node 。我们使用一个队列 queue 来存储节点和其父节点。 visited 集合用于存储已经访问过的节点。

在每次循环中，我们从队列的开头弹出节点（与其父节点）。如果这个节点已经访问过了，则说明图中包含循环或环路，直接返回 True 。如果此节点尚未被访问过，则将其标记为已访问，并遍历该节点的所有邻居。如果某个邻居节点不是该节点的父节点，则将其加入队列中。

最后，在遍历完所有节点后，如果没有发现循环或环路，返回 False 。

接下来，我们演示一下如何使用上述算法检测无向图中是否包含环路：

def has_cycle(graph):
    for node in graph:
        if bfs(graph, node):
            return True
    return False

这里的 has_cycle 函数接受一个图作为参数，并迭代图中的每个节点，使用 bfs 函数判断该节点是否处于循环或环路。如果任何一个节点处于循环或环路当中，则返回 True 。如果整个图中都没有循环或环路，返回 False 。

代码演示

接下来，我们将演示一下如何使用上述代码检查一个无向图是否有环路。我们创建一个无向图，其中节点 1 连接到节点 2 和节点 3 ，节点 2 连接到节点 4 ，节点 3 连接到节点 5 ，节点 4 连接到节点 5 ，节点 5 连接到节点 6 ：

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

node1.neighbors = [node2, node3]
node2.neighbors = [node1, node4]
node3.neighbors = [node1, node5]
node4.neighbors = [node2, node5]
node5.neighbors = [node3, node4, node6]
node6.neighbors = [node5]

现在我们对此无向图运行我们的 has_cycle 函数：

graph = [node1, node2,node3, node4, node5, node6]
print(has_cycle(graph)) # 输出 True

这个测试用例中，图中有一条环路： 1 -> 2 -> 4 -> 5 -> 3 -> 1，所以我们的程序预测输出 True 。

结论

这篇文章演示了如何使用BFS算法来查找无向图是否包含循环或环路的程序。我们首先定义了一个 Node 类作为节点的数据结构，然后实现了 bfs 和 has_cycle 两个函数。 最后，我们用一个测试用例演示了如何检查一个无向图是否有环路。希望本文能够对大家在学习图论的过程中带来帮助。