BFS计算最短路径(python)

以下是 Python 中使用 BFS 计算最短路径的示例代码：

# 定义一个 BFS 函数用于搜索最短路径
def bfs(graph, start, end):
    queue = []
    visited = set()
    queue.append((start, 0))  # 将起点入队并记录到达该点的步数为 0
    visited.add(start)  # 标记起点为已访问
    while queue:
        node, step = queue.pop(0)  # 取出队首元素
        if node == end:
            return step  # 找到终点，返回到达该点的步数
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, step + 1))  # 将邻居入队并记录到达该点的步数
    return -1  # 没有找到最短路径，返回 -1

# 定义一个示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 计算 A 到 F 的最短路径
start = 'A'
end = 'F'
print(bfs(graph, start, end))  # 输出 2

该示例中，先定义了一个 `bfs` 函数用于搜索最短路径。该函数使用队列进行遍历，同时记录每个节点到达起点的步数。如果找到了终点，则返回到达该点的步数，否则返回 -1 表示没有找到最短路径。在示例中，先定义了一个简单的图作为输入，然后计算 A 到 F 的最短路径输出 2。