使用列表存储已访问顶点的BFS最短路径实现时间复杂度是否为O(V²)

问题结论 #

你给出的这个BFS实现的时间复杂度确实是O(V²)，和标准O(V+E)的BFS的核心差异在于已访问节点的存储结构。

原因分析 #

• 标准BFS的O(V+E)复杂度建立在两个前提上：一是每个顶点最多入队1次、每条边最多被遍历1次，这部分总耗时固定为O(V+E)；二是判断节点是否已访问的操作均摊耗时为O(1)，一般通过哈希集合实现。
• 你当前的实现用了Python列表存储已访问的searched，列表的in判断需要遍历全表匹配元素，最坏耗时为O(N)，其中N是已存储的元素数量。
• 最坏情况下（比如遍历无向完全图），每个节点的in判断都要遍历所有已访问过的V个节点，仅判断操作的总耗时就达到O(V²)，远高于边遍历的O(E)，因此整体时间复杂度为O(V²)。

优化方案 #

只需要把已访问存储结构从列表换成集合，就能把复杂度降回标准的O(V+E)，修改点如下：

1. 把searched = []改为searched = set()
2. 把searched.append(person)改为searched.add(person)

修改后代码示例：

from collections import deque
def search(name):
   search_queue = deque()
   search_queue += graph[name]  # graph是存储图结构的字典，键为节点名，值为相邻节点列表

   searched = set()
   while search_queue:
      person = search_queue.popleft()
      if person not in searched:
         if some_checking(person):
            return True
         else:
            search_queue += graph[person]
            searched.add(person)

   return False

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