BFS的时间复杂度分析

Question

我知道关于 BFS 的时间复杂度有很多问题：O(V+E)

然而我仍然很难理解为什么时间复杂度是O(V+E)而不是O(V*E)

我知道O(V+E)代表O(max[V,E]) ，我唯一的猜测是它与图的密度有关，而不是与算法本身有关，不像合并排序那样。复杂度始终为O(n*logn)。

我想到的例子是：

1. 带有 |E| 的有向图 = |V|-1是的，时间复杂度为O(V)
2. 带有 |E| 的有向图 = |V|*|V-1| 事实上，复杂度为 O(|E|) = O(|V|*|V|)，因为每个顶点都有一条到除自身之外的其他顶点的出边

我的方向正确吗？任何见解都会非常有帮助。

Answer 1

您的“思想示例”说明复杂性不是O(V*E)，而是O(E)。确实，与V相比​​， E可能是一个很大的数字，但当您说复杂度为O(E)时，这并不重要。

当图是连通的时，你总是可以说它是O(E)。在时间复杂度中包含V的原因是为了覆盖顶点比边多得多的图（因此是断开连接的）：BFS 算法不仅必须访问所有边，还必须访问所有顶点，包括那些没有边缘，只是检测它们没有边缘。所以我们必须说O(V+E)。