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

BFS的复杂度被认为是线性的，即O（V + E），但是有向完整图中边的总数是V *（V-1），它是图形。那么BFS会花费O（V^2）时间遍历完整的图表吗？广度优先搜索完整图的复杂度是多少？

查看答案。抱歉的不便。我没有看到algirthm是BFS。检查我的答案。 – coderredoc

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

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

2017-08-25 02:50:31

给出这个结果，我们可以得出结论：使用邻接表的最坏情况BFS不是线性的，而是二次的？ –

@UttakarshTikku它在算法的输入大小上是线性的，这是顶点数量的二次方。 –

非常感谢！这非常有帮助！ –

BFS运行在O(V + E)时间提供的图表由邻接表结构表示。

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

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

无论图表如何，您总是会先覆盖起点的邻居。然后再为邻居重复这个。所以你可以看到它总是需要遍历O(V+E)时间，但这是表示使邻接矩阵变得困难。所以它将是O(V^2) 。

_{这是因为我们希望找到每一次什么是相邻的给定的顶点“U”，我们遍历整个数组adjmatrix[u]，这是长度的边缘| V |}

2017-08-25 02:41:33 coderredoc

我在这里得到的是这里的顶点数和边数的关系。完整图中的边数是顶点数的函数，对于完整的有向图精确为V *（V-1）。 –

是的，但表示很重要。这就是我所说的。 – coderredoc

回答