BFS算法python

### Python实现BFS算法

#### BFS算法简介
广度优先搜索（BFS）算法是图论中的一种重要算法，能够用于解决许多问题，例如寻找最短路径、拓扑排序等[^1]。

#### 使用Python实现BFS算法

下面是一个简单的`Graph`类定义以及利用该类执行BFS的方法：

from collections import deque, defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        """添加边"""
        self.graph[u].append(v)

    def bfs(self, start_node):
        """
        执行广度优先搜索
        
        参数:
            start_node (int): 开始节点
            
        返回:
            list: 节点访问顺序列表
        """
        visited = set()  # 记录已访问过的节点集合
        queue = deque([start_node])  # 初始化队列并将起始节点加入其中
        traversal_order = []  # 存储遍历顺序的结果数组

        while queue:
            node = queue.popleft()
            
            if node not in visited:
                visited.add(node)
                traversal_order.append(node)
                
                for neighbour in self.graph[node]:
                    if neighbour not in visited:
                        queue.append(neighbour)

        return traversal_order

这段代码创建了一个名为 `Graph` 的类来表示图结构，并实现了两个主要功能：一是通过调用 `add_edge()` 方法向图中增加一条连接；二是使用 `bfs()` 函数来进行广度优先遍历操作。当给定一个起点作为参数传递给 `bfs()` 后，程序会返回按照层次依次被发现的顶点序列[^2]。

为了更好地理解这个过程，在实际运行时可以打印每次迭代后的状态变化情况，以便观察到具体的执行流程。

#### 应用实例——查找迷宫中的最短路径
除了基本的遍历外，BFS还可以应用于更复杂的场景下解决问题，比如在一个由房间组成的网格状环境中找到从入口到达出口的最佳路线。在这种情况下，每一个位置都可以看作图上的一个结点，而相邻的位置之间存在连通关系，则构成了边的关系。此时采用BFS策略可以帮助我们有效地定位最优解，即距离最近的目标位置[^4]。

需要注意的是，如果涉及到带权图的情况，那么就不能简单地依靠BFS来找寻所谓的“最短路径”，因为这通常意味着要考虑到不同边上所附带的成本因素。对于这种情况下的最短路径计算任务来说，更适合的选择可能是像Dijkstra这样的专门针对加权网络设计出来的优化算法[^5]。