Python算法——广度优先搜索

Python中的广度优先搜索算法详解

广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索树、图等数据结构的算法。在BFS中，我们从起始节点开始，首先访问起始节点，然后逐层访问该节点的邻居节点，直到访问完当前层的所有节点，再按照层次顺序逐层访问下一层的节点。在本文中，我们将详细讨论BFS的原理，并提供Python代码实现。

广度优先搜索的原理

广度优先搜索的核心思想是通过队列来实现层次遍历。其主要步骤如下：

将起始节点加入队列。
从队列中取出一个节点，访问该节点。
将该节点的所有未访问过的邻居节点加入队列。
重复步骤2和3，直到队列为空。
以下是广度优先搜索的Python实现：

python">from collections import deque

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, node, neighbors):
        self.graph[node] = neighbors

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

示例

考虑以下图：

 A -- B -- E
    |    |
    C -- D

使用Graph类创建图：

python">g = Graph()
g.add_edge('A', ['B', 'C'])
g.add_edge('B', ['A', 'D', 'E'])
g.add_edge('C', ['A', 'D'])
g.add_edge('D', ['B', 'C'])
g.add_edge('E', ['B'])