python 宽度优先搜索

宽度优先搜索（BFS）是一种用于图或树的算法，用于遍历或搜索所有的顶点或节点。它从给定的起始顶点或节点开始，逐层地向外探索，直到找到目标顶点或节点为止。在搜索过程中，BFS首先访问起始顶点的所有邻居，然后再访问邻居的邻居，以此类推，直到遍历完整个图或树。这种搜索方式保证了在搜索过程中，所有与起始顶点距离相同的顶点都会被访问到。

在Python中，可以使用队列数据结构来实现宽度优先搜索。以下是一个简单的示例代码，展示了如何使用BFS找到两个节点之间的最短路径：

from collections import deque

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

    while queue:
        node, path = queue.popleft()
        if node == target:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))
                visited.add(neighbor)
    
    return []

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

start_node = 'A'
target_node = 'F'
shortest_path = bfs(graph, start_node, target_node)
print(f"从节点 {start_node} 到节点 {target_node} 的最短路径为: {shortest_path}")

输出结果为：

从节点 A 到节点 F 的最短路径为: ['A', 'C', 'F']