algorithm - 为什么 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)。谁能为我解释一下？

Answer 1

E 不是与每个顶点相邻的边数 - 它实际上是图中边的总数。以这种方式定义它很有用，因为您不一定在每个顶点上都有相同数量的边。

由于在 DFS 结束时每条边都会被访问一次，因此您会从该部分获得 O(E) 复杂度。然后你添加 O(V) 来访问每个顶点一次，总共得到 O(V + E)。