为什么BFS的复杂度是O(V + E)而不是O(V * E)? [英] Why is the complexity of BFS O(V+E) instead of O(V*E)?

问题描述

这里有一些伪代码(忽略我的风格)

Some pseudocode here (disregard my style)

从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).谁能为我解释一下?

Since there are V vertices in the graph, and these V vertices are connected to E edges, and visiting getting connected nodes (equivalent to visiting connected edges) is in the inner loop (the outer loop is the recursion itself), it seems to me that the complexity should be O(V*E) rather than O(V+E). Can anyone explain this for me?

推荐答案

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

E is not the number of edges adjacent to each vertex - its actually the total number of edges in the graph. Defining it this way is useful because you don't necessarily have the same number of edges on every single vertex.

由于在DFS结束时每个边缘都会被访问一次，因此从该部分获得O(E)复杂度.然后，您添加一次访问每个顶点的O(V)并总计获得O(V + E).

Since each edge gets visited once by the time the DFS ends, you get O(E) complexity from that part. Then you add the O(V) for visiting each vertex once and get O(V + E) on total.

这篇关于为什么BFS的复杂度是O(V + E)而不是O(V * E)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！