广度优先搜索 python

广度优先搜索（BFS）是一种图遍历算法，用于在无权图或有权图中寻找从起点到目标节点的最短路径。以下是一个使用Python实现广度优先搜索的示例代码：

from collections import deque

def bfs(graph, start, target):
    visited = set()  # 用于记录已经访问过的节点
    queue = deque()  # 使用队列来辅助实现广度优先搜索
    queue.append(start)

    while queue:
        node = queue.popleft()
        if node == target:
            return True  # 找到目标节点，返回True

        if node not in visited:
            visited.add(node)
            neighbors = graph[node]
            queue.extend(neighbors)

    return False  # 没有找到目标节点，返回False

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

start_node = 'A'
target_node = 'F'
result = bfs(graph, start_node, target_node)
print(f"There exists a path from {start_node} to {target_node}: {result}")

在上述代码中，我们使用了一个队列（deque）来辅助实现广度优先搜索。首先，我们将起始节点加入队列，并在每一轮循环中将队列中的节点出队并进行处理。如果当前节点是目标节点，我们即找到了从起始节点到目标节点的路径，返回True。否则，我们将当前节点标记为已访问，并将其未访问的邻居节点加入队列。如果队列为空且没有找到目标节点，表示不存在从起始