为什么BFS的复杂度是O(V+E)而不是O(V*E)？

Question

这里有一些伪代码（请忽略我的风格）

从v1（已入队）开始：

function BFS(queue Q)
  v2 = dequeue Q
  enqueue all unvisited connected nodes of v2 into Q
  BFS(Q)
end // maybe minor problems here

由于该图中有V个顶点，这些V个顶点连接着E条边，在访问相连节点（等价于访问相连边）时会进入内部循环（外部循环为递归本身），因此我认为其复杂度应该是O(V*E)而不是O(V+E)。有人可以为我解释一下吗？

- OneZero

---

非常简化，没有太多的形式：每个边缘被考虑两次，每个节点被处理一次，因此复杂度必须是边缘数量和顶点数量的常数倍。 - G. Bach

这包括具有避免循环的机制。 - Khaled.K

Answer 1

E不是每个顶点相邻的边数，而是图中的总边数。这样定义是有用的，因为在每个顶点上你并不一定有相同数量的边。

由于在DFS结束时，每条边都被访问一次，所以该部分的复杂度为O（E）。然后你需要加上访问每个顶点一次的O（V），总的时间复杂度为O（V + E）。

- hugomg

---

您的回答比较笼统，可能与深度优先搜索（DFS）和广度优先搜索（BFS）都有关。这也许是您在回答中将BFS错拼为DFS的原因（请注意，问题要求的是BFS）。 - yasen

为什么要将时间复杂度写成O(V+E)，如果每次访问顶点的邻居时，与顶点相连的边的数量都不同呢？ - Sandeep

在这种表示法中，E是图中边的总数。 - hugomg

如果图是用邻接矩阵表示的，那么时间复杂度应该是O(V*V)，对吧？因为每次我们从队列中弹出顶点时，都必须遍历所有顶点以查找相邻的顶点。 - Ujesh Nada