潜入侦探蜥蜴

# 1. 首先，我们需要定义图的结构。在这个问题中，图可以用邻接表来表示。 # 2. 然后，我们需要实现广度优先搜索（BFS）算法来找到从起点到终点的最短路径。 # 3. 在BFS过程中，我们需要记录每个节点的前驱节点，以便最后能够回溯出最短路径。 from collections import deque def find_shortest_path(graph, start, end): # 初始化队列，用于BFS queue = deque([start]) # 记录每个节点的前驱节点，初始化为None predecessors = {node: None for node in graph} # 标记起点已经访问 predecessors[start] = start # BFS过程 while queue: current = queue.popleft() # 如果到达终点，结束搜索 if current == end: break # 遍历当前节点的所有邻居 for neighbor in graph[current]: # 如果邻居节点还没有被访问过 if predecessors[neighbor] is None: # 标记邻居节点的前驱节点为当前节点 predecessors[neighbor] = current # 将邻居节点加入队列 queue.append(neighbor) # 如果终点没有被访问过，说明不存在路径 if predecessors[end] is None: return None # 回溯最短路径 path = [] at = end while at != start: path.append(at) at = predecessors[at] path.append(start) path.reverse() return path # 示例图的邻接表表示 graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } start_node = 'A' end_node = 'F' shortest_path = find_shortest_path(graph, start_node, end_node) print(“最短路径:“, shortest_path)