BFS的时间复杂度分析

Question

我知道关于 BFS 的时间复杂度有很多问题，即：O(V+E)

但是我仍然很难理解为什么时间复杂度是 O(V+E) 而不是 O(V*E)

我知道 O(V+E) 代表 O(max[V,E]) 我唯一的猜测是它与图的密度有关，而不与算法本身有关，不像合并排序，它的时间复杂度总是O(n*logn).

我想到的例子是：

带|E|的有向图= |V|-1 是的，时间复杂度将是 O(V)
带|E|的有向图= |V|*|V-1| 复杂度实际上是 O(|E|) = O(|V|*|V|) 因为每个顶点都有一条到除自身之外的所有其他顶点的出边

我的方向对吗？任何见解都会非常有帮助。

Answer 1

考虑一种情况，当你有一棵树时，甚至可能有循环，你从根开始搜索，你的目标是树的最后一片叶子。在这种情况下，您将在到达目的地之前遍历所有边缘。

例如

在这种情况下，您将在实际找到节点 #3 之前检查 4 条边。

Answer 2

您的“思想示例”说明复杂度不是 O(V*E)，而是 O(E)。的确，E 与 V 相比可以是一个很大的数字，但是当你说复杂度是 时并不重要O(E).

当图形连通时，那么你总可以说它是O(E)。在时间复杂度中包含 V 的原因是为了覆盖顶点比边多得多的图（因此不相连）：BFS 算法不仅需要访问所有边，还有所有顶点，包括那些没有边的顶点，只是为了检测它们没有边。所以我们必须说 O(V+E).

Answer 3

这取决于邻接表是如何实现的。一个正确实现的邻接列表是一个 list/array 个顶点，每个顶点条目都有一个相关边的列表。

关键是边条目直接指向它们对应的顶点array/list条目，它们从不必须通过顶点array/list搜索一个匹配条目，他们可以直接查找。这确保边访问总数为 2E，顶点访问总数为 V+2E。这使得总时间为 O(E+V).

在未正确实现的邻接表中，顶点 array/list 没有被直接索引，因此要从边条目到顶点条目，您必须搜索整个顶点列表，即 O(V)，这表示总时间为O(E*V).

Answer 4

如果您遍历算法，复杂性会很容易消失。令 Q 为 FIFO 队列，最初它包含源节点。 BFS 基本上做了以下事情

while Q not empty
  pop u from Q
  for each adjacency v of u
     if v is not marked
         mark v
         push v into Q

由于每个节点添加一次并删除一次，因此 while 循环完成了 O(V) 次。同样，每次我们弹出 u 时，我们都会执行 |adj[u]| |adj[u]| 的操作是的数量 u.

的邻接点

因此，所有 V 的总复杂度为 Sum (1+|adj[u]|)，即 O(V+E)，因为邻接关系的总和为 O(E)（无向图为 2E，无向图为 E定向的）

Time Complexity Analysis of BFS