广度优先搜索完整图的复杂程度是多少?

Question

BFS的复杂度被称为线性的，即O(V+E(，但有向完整图中的边总数是V*(V-1(，它是图大小的2度函数。那么BFS需要O(V^2(时间来遍历一个完整的图吗？

Answer 1

是的，我假设你已经做了数学。

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

Answer 2

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

在密集的情况下，您也会看到答案将是O(V+E).(表示形式为邻接列表(。

在邻接矩阵的情况下O(V^2).

无论图是怎样的，你总是首先覆盖起点的邻居。然后对邻居也重复这个。因此，您可以看到它始终必须在O(V+E)时间内遍历，但正是这种表示使邻接矩阵变得困难。所以它将O(V^2)₁。

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