为什么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).