BFS求单源最短路径时的运行时错误排查求助

问题背景 #

解决HackerRank的《BFS Shortest Reach》任务：给定每条边权重为6的无向图（节点编号1到n），需通过BFS计算指定起点到其他节点的最短距离，不可达节点返回-1，按节点编号顺序返回不含起点的结果。

实现的Python BFS代码最初用列表作队列（pop(0)效率低），后改用collections.deque优化。小测试用例运行正常，但处理含30000条边的大型图时出现运行时错误，需排查问题。

原代码：

from collections import deque

def bfs(n, m, edges, s):
    # Write your code here
    # create hashmap, containing adj verticies
    resList = [-1] * n 
    
    # processing the input
    adjMap = {}
    for edge in edges:
        if edge[0] not in adjMap:
            newSet = set()
            adjMap[edge[0]] = newSet
        if edge[1] not in adjMap:
            newSet = set()
            adjMap[edge[1]] = newSet 
        adjMap[edge[0]].add(edge[1])
        adjMap[edge[1]].add(edge[0])
        
    
    queue = deque()
    valQueue = deque()
    visited = set()
    # initialise queue
    queue.append(s)
    valQueue.append(0)
    resList[s - 1] = 0
    visited.add(s)

    
    while queue:
        # dequeueNode = queue.pop(0)
        dequeueNode = queue.popleft()
        # dequeueNodeVal = valQueue.pop(0)
        dequeueNodeVal = valQueue.popleft()
        adjSet = adjMap[dequeueNode]
        
        for adj in adjSet:
            if adj not in visited:
                visited.add(adj)
                queue.append(adj)
                valQueue.append(dequeueNodeVal + 6)
                resList[adj - 1] = dequeueNodeVal + 6
    resList.remove(0)
    
    
    return resList

问题排查与修复 #

1. 孤立节点引发的KeyError #

原代码仅为出现在edges中的节点创建邻接表条目，若图中存在孤立节点（无任何边连接），当起点为孤立节点时，adjMap[dequeueNode]会抛出KeyError，因为该节点不在adjMap中。

修复方式：初始化邻接表时包含所有1到n的节点，每个节点对应空集合：

adjMap = {i: set() for i in range(1, n+1)}

2. resList.remove(0)的潜在风险 #

resList.remove(0)会删除列表中第一个出现的0，若存在异常情况（如错误设置其他节点距离为0）会导致结果错误；此外，当n=1时，删除后返回空列表虽符合要求，但按索引排除起点更稳妥。

修复方式：通过索引过滤掉起点对应的结果：

return [dist for idx, dist in enumerate(resList) if (idx + 1) != s]

3. 大图场景下的内存与效率优化 #

• 原代码用两个队列分别存储节点和距离，可合并为存储元组的单个队列，简化代码并减少内存占用。
• 单独的visited集合会占用额外内存，可利用resList的初始值-1判断节点是否未访问（未访问时距离为-1），省去visited集合。

修正后代码 #

from collections import deque

def bfs(n, m, edges, s):
    resList = [-1] * n 
    
    # 初始化所有节点的邻接表，避免孤立节点的KeyError
    adjMap = {i: set() for i in range(1, n+1)}
    for edge in edges:
        u, v = edge
        adjMap[u].add(v)
        adjMap[v].add(u)
        
    queue = deque()
    queue.append( (s, 0) )
    resList[s - 1] = 0

    while queue:
        dequeueNode, dequeueNodeVal = queue.popleft()
        adjSet = adjMap[dequeueNode]
        
        for adj in adjSet:
            if resList[adj - 1] == -1:  # 用resList判断访问状态，替代visited集合
                resList[adj - 1] = dequeueNodeVal + 6
                queue.append( (adj, dequeueNodeVal + 6) )
    
    # 按节点顺序排除起点，构造结果
    return [dist for idx, dist in enumerate(resList) if (idx + 1) != s]

内容的提问来源于stack exchange，提问作者Alex