什么是BFS的时间复杂度取决于图表的表示？

Question

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

• 邻接矩阵
• 邻接名单
• 边缘清单

它们的空间复杂性是否相同？

Answer 1

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

为什么在Adjacency Matrix的情况下更多？

这主要是因为每当我们想要找到与给定顶点'U'相邻的边时,我们就必须遍历整个数组AdjacencyMatrix[U],这是不合适的|V|.

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

当由邻接矩阵和矩阵实现时BFS的复杂度差异是由于这样的事实:在邻接矩阵中,为了告知哪个节点与给定顶点相邻,我们采用O(| V |)时间,而不考虑边缘.然而,在邻接列表中,它立即可供我们使用,花费时间与相邻顶点本身成比例,这对于所有顶点的总和| V | 是| E |.因此,邻接列表的BFS给出O(| V | + | E |).

Answer 2

时间复杂性必然取决于表示.

如该链接所示,时间复杂度和邻接列表是O(V + E),并且邻接矩阵是O(V ²).