连通分量计数算法的运行时间

Question

我一直在研究连接组件，并在Wikipedia上看到了这个描述：

使用广度优先搜索或深度优先搜索在线性时间内计算图的连通分量（根据图的顶点和边的数量）很简单。在任何一种情况下，从某个特定顶点 v 开始的搜索将在返回之前找到包含 v（并且仅此而已）的整个连接组件。要查找图的所有连接组件，请遍历其顶点，每当循环到达尚未包含在先前找到的连接组件中的顶点时，开始新的广度优先或深度优先搜索。

此操作的运行时间是多少？我遇到过一些消息来源说连接的组件是O(n)及时完成的。然而，据我所知，在最坏的情况下，每个顶点都是它自己的连接组件，这个算法必须执行 n 个 DFS/BFS 操作，每个操作都是它自己的O(n)时间。因此，不应该是 this 的运行时间O(n^2)吗？

Answer 1

首先，使用 DFS 或 BFS遍历G(V, E)具有|V|顶点和|E|边的单个连接组件具有O(|V|+|E|)复杂性。

线性时间（就图的顶点和边的数量而言）

让我们假设图G(V, E)具有k连接的组件。

G(V, E) = G1(V1, E1) ? G2(V2, E2) ? ... ? Gk(Vk, Ek)

每个组件Gi都可以在 DFS/BFS 中找到O(|Vi|+|Ei|)。因此，对于每个未访问的顶点启动 DFS 或 BFS 以遍历其连通分量的算法总时间为：

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|)

这些组件没有任何公共顶点或边，因为它们没有连接。所以：

|V| = |V1| + |V2| + ... + |Vk|
|E| = |E1| + |E2| + ... + |Ek|

最后，连通分量的整体计算复杂度为：

O(|V1|+|E1|) + O(|V2|+|E2|) + ... + O(|Vk|+|Ek|) + O(|V|) =
O(|V1|+|V2|+...+|Vk| + |E1|+|E2|+...+|Ek|) + O(|V|) =
O(|V|+|E|) + O(|V|) =
O(|V|+|E|)