data-structures - 根据图的表示，BFS 的时间复杂度是多少？

Question

我想知道 BFS 的时间复杂度是多少，如果我使用:

邻接矩阵

邻接表

边缘列表

它与它们的空间复杂度相同吗？

Answer 1

使用邻接矩阵实现的 BFS 的复杂度为 O(|V|²) .并且当由邻接列表实现时是 O(|V| + |E|) .

Why is it more in the case of Adjacency Matrix?

这主要是因为每次我们想要找到与给定顶点“U”相邻的边是什么时，我们都必须遍历整个数组 AdjacencyMatrix[U] ，当然是长度 |V| .
想象一下 BFS 作为前沿进展。你取一个起始顶点 S ，在级别 0 .与 S 相邻的所有顶点将在级别 1 .然后，我们将层1的所有顶点的所有相邻顶点都标记为层 2。 .因此，每个顶点将只属于一个边界。这些边界中的每一个都对应于不同的层次。当一个元素位于边界时，我们检查一次它的相邻顶点，这需要 O(|V|)时间。如，边疆覆盖 |V|元素在算法过程中，总时间将变为 O(|V| * |V|)这是 O(|V|²) .
由邻接表和矩阵实现时 BFS 的复杂度差异是由于在邻接矩阵中，为了确定哪些节点与给定的顶点相邻，我们取 O(|V|)时间，与边数无关。而在 Adjacency List 中，我们可以立即使用边，因此它花费的时间与相邻顶点的数量成正比，即对所有顶点求和 |V|是 |E|。因此，邻接表的 BFS 给出了 O(|V| + |E|)。