从三道LeetCode题目掌握广度优先搜索（BFS）

广度优先搜索（BFS）是一种常见的图遍历算法，它按照层次顺序搜索图中的节点。在LeetCode中，有许多问题可以通过BFS得到解决。本文将通过三道具有代表性的题目，深入探讨如何应用BFS算法。

第一题：无向图的最短路径（广度优先搜索）

题目描述：给定一个无向图，请编写一个函数，计算从起点到终点的最短路径。可以使用广度优先搜索（BFS）算法解决该问题。

解题思路：使用BFS算法可以轻松解决无向图的最短路径问题。首先，创建一个队列用于存储待处理的节点，并将起点入队。同时，创建一个集合用于存储已访问过的节点，以避免重复访问。然后，开始BFS循环，在每一轮循环中，出队一个节点并访问其所有未访问过的邻居节点，将邻居节点入队并标记为已访问。重复此过程直到终点被访问到或队列为空。

示例代码（Python）：

from collections import deque
def bfs(graph, start, end):
    queue = deque([start])
    visited = set([start])
    while queue:
        vertex = queue.popleft()
        if vertex == end:
            return True
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return False

注意事项：在实现BFS时，需要注意队列和集合的数据结构选择。队列用于按顺序存储待处理的节点，而集合则用于快速判断节点是否已被访问过。同时，要确保图中不存在环路，否则BFS无法正确计算最短路径。

第二题：丑数II（广度优先搜索）

题目描述：给定一个正整数n，返回长度为n的连续正整数序列中所有丑数之和。丑数定义为不是完全平方数的正整数。可以使用广度优先搜索（BFS）算法来解决问题。

解题思路：为了解决这个问题，我们可以使用BFS来生成长度为n的连续正整数序列，并检查每个数是否为丑数。丑数不是完全平方数，因此我们可以使用一个简单的数学性质来判断一个数是否为丑数：如果一个数k不是完全平方数，那么一定存在一个数i满足1 <= i <= k-1且k mod i == 0且i <= sqrt(k)。利用这个性质，我们可以从1开始逐个生成连续正整数序列，并使用BFS检查每个数是否为丑数。最后返回所有丑数的和即可。

示例代码（Python）：

from collections import deque
from math import sqrt
def ugly_numbers(n):
    ugly_sum = 0
    queue = deque([1])  # 起始值为1的队列
    visited = set([1])  # 记录已访问的数
    while len(queue) < n:  # 队列长度小于n时继续循环
        num = queue.popleft()  # 出队一个数
        ugly_sum += num  # 累加到丑数和中
        for i in range(1, int(sqrt(num)) + 1):  # 遍历可能的因子i
            if num % i == 0 and num // i != num // i.real:  # 判断是否为丑数因子
                visited.add(num // i)  # 将丑数因子入队并标记为已访问
                queue.append(num // i)  # 将丑数因子入队等待后续判断和处理
    return ugly_sum  # 返回丑数之和

注意事项：在实现BFS时，需要注意队列和集合的数据结构选择。队列用于按顺序存储待处理的数，而集合则用于快速判断数是否已被访问过。同时，要确保生成的连续正整数序列中不存在重复的数。另外，为了避免重复计算和存储过大的数，可以使用集合来记录已访问过的数。在判断一个数是否为丑数时，可以利用数学性质来优化判断过程。

第三题：单词接龙（广度优先搜索）

题目描述：给定两个字符串words1和words2，请你从