### Python 实现广度优先搜索 (BFS) 计算无权图最短单源路径 以下是基于题目描述的 Python 实现代码，用于计算无权图中最短单源路径： ```python from collections import deque def bfs_shortest_path(n, edges, start, target): """ 使用 BFS 找到无权图中从起点到终点的最短距离。 参数: n (int): 图中的节点总数。 edges (list of tuples): 边列表，每条边表示两个相连的节点。 start (int): 起始节点编号。 target (int): 目标节点编号。 返回: int: 从起始节点到目标节点的最短距离。如果无法到达，则返回 -1。 """ # 构建邻接表 adj_list = {i: [] for i in range(1, n + 1)} for u, v in edges: adj_list[u].append(v) adj_list[v].append(u) # 初始化队列和访问集合 queue = deque([(start, 0)]) # 队列存储当前节点及其距离 visited = set([start]) # 已访问节点集 while queue: current_node, distance = queue.popleft() # 如果找到目标节点，立即返回距离 if current_node == target: return distance # 处理相邻节点 for neighbor in adj_list[current_node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance + 1)) # 如果遍历结束仍未找到目标节点，返回 -1 表示不可达 return -1 # 输入处理部分 if __name__ == "__main__": # 第一行为节点数量 n = int(input().strip()) edges = [] # 接收多行输入直到 EOF 或者空白行为止 try: while True: edge_input = input().strip() if not edge_input: break u, v = map(int, edge_input.split()) edges.append((u, v)) except EOFError: pass # 假设起始点为 1，目标点为 n（可根据实际需求调整） start = 1 target = n result = bfs_shortest_path(n, edges, start, target) print(result) ``` #### 解释 上述代码实现了广度优先搜索算法来解决无权图上的最短路径问题[^1]。 - **输入**: - 第一行是一个整数 `n`，表示节点的数量。 - 后续若干行是边的信息，每一行包含两个整数 `u` 和 `v`，表示一条连接节点 `u` 到节点 `v` 的无向边。 - **输出**: - 输出是从起始节点到目标节点的最短距离。如果没有路径可达，则输出 `-1`。 此方法利用了队列结构逐层扩展节点的特点，从而保证首次抵达目标节点时所经过的距离是最短的[^3]。 --- ###