BFS算法之地铁路线问题代码
时间: 2024-05-01 16:19:11 浏览: 6
以下是使用BFS算法解决地铁路线问题的Python代码示例:
```python
from queue import Queue
# 地铁站点信息,每个元素为一个元组,分别表示站点名称和与该站点相邻的站点列表
stations = [
("A", ["B", "C"]),
("B", ["A", "D"]),
("C", ["A", "E"]),
("D", ["B", "E", "F"]),
("E", ["C", "D", "F"]),
("F", ["D", "E"])
]
# BFS算法求解最短路径
def bfs(start, end):
visited = set() # 已经访问过的站点集合
q = Queue() # 队列,用于存储待访问的站点
q.put((start, 0)) # 起点入队,初始距离为0
visited.add(start) # 起点标记为已访问
while not q.empty():
current, distance = q.get() # 取出队首站点及其距离
if current == end: # 如果到达终点,则返回距离
return distance
for neighbor in get_neighbors(current): # 遍历当前站点的相邻站点
if neighbor not in visited: # 如果相邻站点未被访问过
q.put((neighbor, distance + 1)) # 将相邻站点入队,并计算距离
visited.add(neighbor) # 标记相邻站点为已访问
return -1 # 如果无法到达终点,则返回-1
# 获取指定站点的相邻站点列表
def get_neighbors(station):
for s in stations:
if s[0] == station:
return s[1]
return []
# 测试代码
print(bfs("A", "F")) # 2
print(bfs("B", "E")) # 1
print(bfs("C", "D")) # 2
print(bfs("A", "G")) # -1
```