广度优先搜索完全图的复杂度是多少？

Question

据说 BFS 的复杂度是线性的，即 O(V+E)，但有向完全图中边的总数是 V*(V-1)，这是图的大小。那么 BFS 是否需要 O(V^2) 时间来遍历一个完整的图？

Answer 1

BFS 在 O(V + E) 时间内运行，前提是图形由邻接表结构表示。

同样在密集的情况下，您会看到答案将是 O(V+E)。（表示是邻接表）。

如果是邻接矩阵 O(V^2)。

无论图形如何，你总是首先覆盖起点的邻居。然后也对邻居重复此操作。所以你可以看到它总是必须在 O(V+E) 时间内遍历，但它是让邻接矩阵变得困难的表示。所以它将是 O(V^2)₁.

₁_{这是因为每次我们要查找与给定顶点'u'相邻的边有哪些时，我们遍历整个数组adjmatrix[u]，长度为|V|}

Answer 2

是的，我假设你已经计算过了。

O(V+E) = O(V + V*(V-1))
       = O(V + V*V - V)
       = O(V*V)

What is the complexity of breadth first search for a complete graph?