Python程序：使用BFS在图中查找可到达节点达到从节点

在图的计算中，BFS即广度优先搜索是最常用的算法。它被广泛用于网络爬虫、搜索及许多其他领域的图像处理。

在本篇文章中，我们将介绍如何使用Python实现BFS算法，以查找从给定节点出发可到达的所有节点。

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

BFS算法简述

BFS算法从给定的起点开始，逐层遍历与其相连的节点，并记录其访问情况，直到遍历到相应的终点，或者遍历到所有可到达的节点。

其基本思想是通过队列来实现节点的遍历顺序，先访问到的节点先处理，后访问到的节点先存放到队列中等待处理。

BFS算法实现代码

接下来，我们将介绍如何使用Python实现BFS算法。

首先，需要定义一个节点类，包括节点编号与邻居节点：

class Node:
    def __init__(self, n):
        self.n = n
        self.neighbors = []
    def addNeighbor(self, neighbor):
        self.neighbors.append(neighbor)

接着，定义一个搜索函数，以起点为参数，使用队列实现节点的遍历：

def bfs(start):
    visited = set()
    queue = [start]

    while len(queue) > 0:
        node = queue.pop(0)
        visited.add(node)
        print(node)

        for neighbor in node.neighbors:
            if neighbor not in visited:
                queue.append(neighbor)

最后，构建一个图，并执行搜索：

# 构建图
nodes = [Node(i) for i in range(6)]
nodes[0].addNeighbor(nodes[1])
nodes[0].addNeighbor(nodes[2])
nodes[1].addNeighbor(nodes[2])
nodes[2].addNeighbor(nodes[0])
nodes[2].addNeighbor(nodes[3])
nodes[3].addNeighbor(nodes[3])
nodes[4].addNeighbor(nodes[5])

# 执行搜索
bfs(nodes[2])