breadth-first-search - 使用邻接矩阵表示的广度优先搜索的时间复杂度？

Question

在 bfs 中，我们必须查找每个节点，对于每个节点，我们必须查看行的所有元素。这不需要 O(V^2)(邻接矩阵中的元素数)时间，因此对于邻接矩阵不应该总时间为 O(V^2+E)。

Answer 1

使用邻接矩阵实现的 BFS 的复杂度为 O(|V|2)。这主要是因为每次我们想要找到与给定顶点“U”相邻的边是什么时，我们都必须遍历整个数组 AdjacencyMatrix[U]，它偏离了长度 |V|。

想象一下 BFS 作为前沿进展。你取一个起始顶点 S，它在级别 - 0。所有相邻的顶点都在级别 - 1。然后，我们将级别 - 1 的所有顶点的所有相邻顶点都标记为级别- 2. 因此，每个顶点将只属于一个边界(或级别)。当一个元素位于边界时，我们检查一次它的相邻顶点，这需要 O(|V|) 时间。因为，边界覆盖 |V|算法过程中的元素，总时间将变为 O(|V| * |V|)，即 O(|V|2)。

当由邻接表和矩阵实现时，BFS 中的复杂性差异发生的原因在于，在邻接矩阵中，要判断哪些节点与给定的顶点相邻，我们需要 O(|V|) 时间，而不管边如何。而在 Adjacency List 中，它对我们来说是立即可用的，花费的时间与相邻顶点本身成正比，即对所有顶点求和 |V|是 |E|。因此，邻接表的 BFS 给出了 O(|V| + |E|)。

我希望我的回答对您有所帮助，如果有帮助，请告诉我...! ☺