13

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

  • 邻接矩阵
  • 邻接表
  • 边缘列表

和它们的空间复杂度一样吗？

4

4 回答 4

19

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

为什么在邻接矩阵的情况下更多？

这主要是因为每次我们想要找到与给定顶点“U”相邻的边是什么时，我们都必须遍历整个数组AdjacencyMatrix[U]，这当然是长度|V|。

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

由邻接列表和矩阵实现时 BFS 的复杂性差异是由于在邻接矩阵中，为了确定哪些节点与给定顶点相邻，我们需要O(|V|)时间，而与边的数量无关。而在邻接表中，边是我们立即可用的，因此它所花费的时间与相邻顶点的数量成正比，所有顶点的总和 |V| 是|E|。因此，BFS by Adjacency List 给出 O(|V| + |E|)。

于 2015-02-09T18:39:07.923 回答
5

时间复杂度必然取决于表示。

正如这个链接所暗示的，邻接列表的时间复杂度是 O(V + E)，邻接矩阵的时间复杂度是 O(V 2 )。

于 2014-01-28T06:18:10.403 回答
2

首先让我们看一下时间复杂度。如果邻接矩阵可以存储为稀疏矩阵，空间复杂度将是相同的。稀疏矩阵本质上只存储邻接矩阵的非零值，因此具有与邻接表表示相同的空间复杂度，即 O(|V| + |E|)

现在谈谈时间复杂度。进行 BFS 搜索的一种方法是简单地使用稀疏邻接矩阵，因为通常使用邻接列表表示，即 O(|V| + |E|)。

对邻接矩阵进行 BFS 的另一种方法是通过重复应用 Y=GX 来使用稀疏矩阵向量乘法，其中 G 是稀疏邻接矩阵，X 是边界上为 1 的稀疏向量。此操作基本上是 G 的列的组合。如果执行此操作以使每次乘法所花费的时间与 G 的每一列中访问的数据大小和向量 X 中的非零数成正比，那么时间复杂度将为也是 O(|V| + |E|)。这种方法的一个优点是，通过将 X 替换为代表多个 BFS 搜索边界的稀疏矩阵，可以直接将其扩展到多个 BFS 搜索。在这篇论文中可以看到更多关于使用稀疏矩阵实现图算法的细节。

边缘列表通常不用于 BFS，因为查找顶点的邻居很昂贵。

于 2016-11-02T15:53:46.820 回答
0

Graph 不同表示的时间复杂度：

1.边缘列表：

边列表由列表中的所有边组成。为了进行 BFS 时间复杂度是O(E^2)。因为对于每条边u->v，您必须遍历整个边列表并找到源顶点所在的边u并探索它们，然后探索u->v要进行 BFS 的顶点“v”。

E边数在哪里。

如果根据源索引和目标索引对边进行排序，则排序列表将按 BFS 顺序排列。只需遍历列表，您将获得 BFS。

时间复杂度O(E*log(E))用于对边缘列表进行排序。

2.邻接表

邻接是一个键映射，其中每个顶点都是一个键，并指向一个顶点列表，这些顶点与该键顶点相关或相邻。

为了执行 BFS，将任何顶点放入队列中并使其成为已访问，弹出队列 [0]，选择起始顶点，探索其所有相邻顶点，将它们设为已访问并将它们放入队列并类似地弹出queue[0] 并探索所有未访问的顶点，直到队列变空。对于每个顶点，您只遍历其相邻的未访问顶点（除了边之外什么都没有）。

所以，时间复杂度是O(V+E)

3.矩阵

在矩阵表示中，对于每个顶点，都必须遍历所有顶点，检查是否有未访问过的顶点。因为，对于每个顶点，我们都在遍历所有顶点，

时间复杂度为O(V^2)

于 2020-09-13T17:42:27.423 回答