BFS 获取从给定起始节点到每个节点的距离的运行时错误

Question

我正在做HackerRank问题BFS最短到达：

考虑一个无向图，其中每条边的权重为 6 个单位。每个节点都从 1 到 n 连续标记。

您将收到一些询问。对于每个查询，您将获得描述无向图的边列表。创建图的表示后，必须使用广度优先搜索算法 (BFS) 确定并报告从给定起始位置到其他每个节点的最短距离。按节点编号顺序返回距起始节点的距离数组。如果某个节点无法访问，则为该节点返回 −1。

示例

下图基于列出的输入：

n = 5  // number of nodes
n = 3 // number of edges
edges = [1, 2], [1, 3], [3, 4]
s = 1 // starting node

所有距离均从起始节点 1 开始。计算输出到节点 2 到 5 的距离：[6, 6, 12, -1]。每条边有6个单位，不可达节点5所需的返回距离为-1。

功能说明

完成

bfs

功能。如果某个节点不可达，则其距离为 -1。

bfs

具有以下参数：

• int n

  ：节点数

• int m

  ：边数

• int edges[m][2]

  ：边的起始和结束节点

• int s

  ：开始遍历的节点

退货

int[n-1]

：按节点编号递增顺序到节点的距离，不包括起始节点（如果节点不可到达，则为-1）

我的尝试

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

最初我的队列只是一个列表，因此：

queue = []
queue.append(blah)
queue.pop(0)

我会从列表的开头弹出，我知道这是低效的，因为它需要重新索引。不管怎样，我把它从

deque

改为

collections

模块，因为我知道这样效率更高。

问题

我的解决方案未通过六个测试之一。对于非常大的输入大小，它似乎遇到了运行时错误。黑客排名仅显示：

编译器消息：运行时错误

输入由 6 个测试用例组成，每个测试用例代表大图（例如 30000 条边......）。

我已经优化了我认为可以的一切：我正在使用线性运行算法。我认为唯一可能扰乱我的时间效率的可能是处理输入部分，我将所有内容放入哈希映射中。然而，这只是 O(edges)，即给定的

edges

数组的大小。

预期的输出很大，我看不出如何有效地调试如此大的输入/输出，并且我无法用小输入重现问题：

我错过了什么？我明天有一个编码面试...

Answer 1

当

s

是没有边的节点时，就会出现问题。在这种情况下，您的

adjMap

将没有

s

的条目，并且在主循环的第一次迭代中，在以下语句中将出现运行时错误：

adjSet = adjMap[dequeueNode]

一旦意识到这一点，解决这个问题就很简单了，而且有很多方法可以做到。例如，您可以替换以下语句：

adjMap = {}

这个：

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

...然后您还可以删除第一个循环中的

if

语句。

其他改进

通过上述更改，它会起作用，但我想借此机会建议一些其他更改：

• adjMap

  可以是一个列表而不是字典，使用与

  resList

相同的原理
• 您可以省略

  visited

  ，而是检查

  resList

  在节点索引处是否有 -1。如果是，则该节点还没有被访问过
• 您可以省略第二个双端队列，因为可以从

  resList

  检索该值。
• 您可以调用

  .remove(0)

  来代替

  pop

  来删除相同的起始节点条目。
• 您可以从一开始就将节点号转换为基于 0 的索引，这样主循环中的所有索引都不会进行这种负 1 修正。
• 避免在循环的每次迭代中添加 6。在循环之前获得值时执行此操作
• 邻居集合不一定是一个集合，它可以是一个简单的列表，因此邻接列表是一个 2D 列表。

这会产生以下代码：

def bfs(n, m, edges, s):
    resList = [-1] * n
    
    # Create the adjacency list as a 2D list and initialise all entries
    adjMap = [[] for _ in range(n)]
    # Populate the adjacency list, and convert immediately to 0-based indexing
    for a, b in edges:
        adjMap[a - 1].append(b - 1)
        adjMap[b - 1].append(a - 1)
    s -= 1  # ...also the start index
        
    queue = deque((s, ))
    resList[s] = 0
    
    while queue:
        dequeueNode = queue.popleft()
        # Read the value from our result list and immediately add the 6
        distance = resList[dequeueNode] + 6
        
        for adj in adjMap[dequeueNode]:
            if resList[adj] < 0:  # This value can serve for "visited" detection
                queue.append(adj)
                resList[adj] = distance
    resList.pop(s)  # No need to search for a 0. We know where it is.
    return resList