广度优先搜索（Breadth-First Search，简称BFS）是一种遍历或搜索树或图的算法。它从根节点开始，沿着树的宽度遍历树的节点，如果所有节点都被访问过，则算法结束。BFS通常用于解决最短路径问题、图遍历等。

BFS的基本原理

BFS的核心思想是使用一个队列来存储待访问的节点，并按照节点的访问顺序进行遍历。以下是BFS的基本步骤：

  1. 将起始节点加入队列。
  2. 当队列为空时，算法结束。
  3. 从队列中取出一个节点，访问它。
  4. 将该节点的所有未访问过的邻接节点加入队列。

BFS在LeetCode中的应用

LeetCode上有许多与BFS相关的题目，以下是一些例子：

  • 200. 岛屿数量：给定一个由 '1' 和 '0' 组成的二维网格，计算岛屿的数量。我们可以使用BFS来遍历每个岛屿，并计算岛屿的数量。
  • 127. 单词接龙：给定两个单词，找出它们之间的最短转换序列。在转换序列中，每个中间单词必须遵循以下规则：它必须在字典中，并且它的长度必须与单词相同。我们可以使用BFS来找到最短的转换序列。
  • 752. 打开转盘锁：给定一个密码锁，你需要通过转盘来解开它。每个转盘可以顺时针或逆时针旋转，并且每次旋转都会改变密码。你可以使用BFS来找到解开密码锁的最少旋转次数。

BFS的代码实现

以下是一个使用Python实现的BFS算法示例：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                queue.append(neighbor)
    return visited

在这个例子中，graph 是一个表示图的字典，start 是起始节点。

总结

BFS是一种强大的图遍历算法，在LeetCode中有着广泛的应用。通过理解BFS的基本原理和代码实现，你可以更好地解决与图相关的题目。如果你对BFS还有疑问，可以访问我们的LeetCode专题了解更多信息。

Breadth-First Search