使用广度优先遍历求无向图的最短路径

广度优先遍历可以用来求无向图的最短路径。具体步骤如下：

1. 定义一个队列，将起点入队，并标记起点已访问。
2. 当队列不为空时，取出队首顶点进行处理。
3. 遍历该顶点的所有邻接顶点，如果邻接顶点未被访问，则将其入队，并标记为已访问，同时记录该邻接顶点的前驱顶点为当前顶点。
4. 重复步骤2和3，直到队列为空或者找到了目标顶点。
5. 如果找到了目标顶点，可以通过前驱顶点逆序遍历得到最短路径。

下面是 Python 代码实现：

from collections import deque

def bfs_shortest_path(graph, start, end):
    # 初始化队列和访问标记
    queue = deque([start])
    visited = {start: None}

    while queue:
        vertex = queue.popleft()
        # 如果找到目标顶点，则结束搜索
        if vertex == end:
            break
        # 遍历邻接顶点
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited[neighbor] = vertex

    # 如果没有找到目标顶点，说明不存在从起点到目标顶点的路径
    if end not in visited:
        return None

    # 通过前驱顶点逆序遍历得到最短路径
    path = [end]
    while path[-1] != start:
        path.append(visited[path[-1]])
    return path[::-1]

其中，`graph` 是无向图的邻接表表示，`start` 和 `end` 分别是起点和目标顶点。函数返回从起点到目标顶点的最短路径（如果存在），否则返回 `None`。