[数据结构与算法]Python广度优先遍历BFS中使用list.pop(0)超过时间限制的解决办法

楼主遇到这个问题是在LeetCode刷题时遇到2039. 网络空闲的时刻这个题目，按照BFS模板写的最后一个测试案例怎么都过不去（甚至复制官方的都过不去），幸得高人指点才发现问题所在。
题目描述：

我原始的代码为：

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        graph = [[] for _ in range(n)]
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        
        # 广度优先遍历
        queue = [0] 
        distance = [-1 for _ in range(n)] #得到每一个节点到0节点的最短距离
        visited = [False] * n
        visited[0] = True
        dis_cur = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                node = queue.pop(0)
                distance[node] = dis_cur
                for adj in graph[node]:
                    if visited[adj] == False:
                        queue.append(adj)
                        visited[adj] = True
            dis_cur += 1
        
        #遍历每个节点计算其变成空闲状态的最晚时间
        res = 0
        for i in range(1,n):
            time = patience[i] * ((2*distance[i] - 1) // patience[i]) + 2 * distance[i] + 1
            res = max(res,time)
        return res 

这里会超出时间限制的原因是：使用list.pop(0)的时间复杂度为O(n)，在BFS那块达到了$O(n^2)$，所以在面对$10^5$数据大小时会超出时间限制。

解决方法有两个：

1. 使用两个list来回倒
2. 使用Python库自带的双端队列collections.deque()

需要说明的是list是一张顺序表，在使用list.pop(0)时需要使所有的元素向前平移，时间复杂度为O(n)，而deque是链表，在头部插入或删除节点时间复杂度为O(1)。

先说方法一，使用两个list来回替换代替了queue.pop(0)，避免了一次多余的循环：
该部分代码来自LeetCode用户Meteordream对我的评论，感谢大佬！

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        graph = [[] for _ in range(n)]
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        
        # 广度优先遍历
        queue = [0] 
        distance = [-1 for _ in range(n)] #得到每一个节点到0节点的最短距离
        visited = [False] * n
        visited[0] = True
        dis_cur = 0
        while queue:
            # 这里用另外一个list
            tmp = list()
            # 不要 pop 了，直接遍历，新加入的放到新list
            for node in queue:
                distance[node] = dis_cur
                for adj in graph[node]:
                    if visited[adj] == False:
                        tmp.append(adj)
                        visited[adj] = True
            dis_cur += 1
            # 新 list 换掉旧 queue
            queue = tmp
        
        #遍历每个节点计算其变成空闲状态的最晚时间
        res = 0
        for i in range(1,n):
            time = patience[i] * ((2*distance[i] - 1) // patience[i]) + 2 * distance[i] + 1
            res = max(res,time)
        return res

方法二：
使用Python自带的双端队列方法

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        graph = [[] for _ in range(n)]
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        
        # 广度优先遍历
        queue = collections.deque() #替换为双端队列
        queue.append(0)
        distance = [-1 for _ in range(n)] #得到每一个节点到0节点的最短距离
        visited = [False] * n
        visited[0] = True
        dis_cur = 0
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                distance[node] = dis_cur
                for adj in graph[node]:
                    if visited[adj] == False:
                        queue.append(adj)
                        visited[adj] = True
            dis_cur += 1

        
        #遍历每个节点计算其变成空闲状态的最晚时间
        res = 0
        for i in range(1,n):
            time = patience[i] * ((2*distance[i] - 1) // patience[i]) + 2 * distance[i] + 1
            res = max(res,time)
        return res