相关疑难解决方法(0)

例如,遍历顶点的每个相邻边的时间复杂度O(N),其中N是相邻边的数量.因此,对于V个顶点,时间复杂度变为O(V*N)= O(E),其中E是图中边的总数.由于从队列中删除和添加顶点是O(1),为什么它被添加到BFS的总体时间复杂度中O(V+E).

网站http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html描述了当使用邻接列表时,DFS和BFS具有复杂度O(V + E),如果使用邻接矩阵,复杂度为O(V ²).为什么是这样？

这里有一些伪代码(无视我的风格)

从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).有人能为我解释一下吗？

我知道堆栈溢出中存在类似的问题,其中一个人问过,为什么BFS/DFS的时间复杂度不仅仅是O(V).

给出的适当答案是在完整图的情况下E可以与V ^ 2一样大,因此在时间复杂度中包括E是有效的.

但是,如果V不能大于E + 1.那么,在那种情况下,时间复杂度中没有V,应该有效吗？