存储已检查顶点的图最短路径

Question

我知道通过 BFS 的最短路径的时间复杂度是 O(V+E)。但是我在 Python 上找到了一个算法的实现，它看起来像这样。

def search(name):
   search_queue = deque()
   search_queue += graph[name]  # graph is a dict<string: list of strings>

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

   return False

在外循环中，我们遍历图中的每个顶点，每次迭代我们检查该顶点是否已经被访问过。由于 searched 是一个列表，因此搜索将进行 O(N) 次操作。我说的时间复杂度在这个实现中是 O(V^2) 对吗？

Answer 1

是的，你是对的。搜索节点是否已被访问最多可能需要 O(V) 次，并且完成 O(V) 次。此代码是 O(V^2).

可以通过更改用于存储访问节点的数据结构轻松改进。从列表更改为集合，将使此代码在 O(V + E).

中有效