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

Question

我一直在研究联通分量，并在维基百科上看到了这个描述：

计算图的连通分量可以使用广度优先搜索或深度优先搜索在线性时间内（以图的顶点和边数为单位）轻松完成。无论哪种情况，从某个特定的顶点v开始的搜索将在返回之前找到包含v的整个连通分量（且不超过），以寻找图的所有连通分量，请循环遍历其顶点，并在循环到达尚未包括在先前发现的连通分量中的顶点时启动新的广度优先或深度优先搜索。

这个操作的运行时间是多少？我已经看到有些来源说连接组件在O(n)时间内完成。然而，从我所知道的来看，在最坏的情况下，每个顶点都是它自己的连通分量，这个算法就必须执行n个DFS / BFS操作，每个操作本身都是O(n)时间。因此，这个操作的运行时间不应该是O(n^2)吗？

- MMMMMCK

---

如果所有顶点都是不相连的，那么每个广度优先搜索都会在其起始顶点结束，并且时间复杂度为O(1)。你必须从另一个角度来论证：无论你以何种方式进行搜索，你永远不会访问一个顶点超过一次，因此整个操作的时间复杂度为O(n)。 - undefined

DFS或BFS需要O(N)的时间，但这里的N是不同的。你必须追踪的所有连通分量的大小之和等于整个图的大小。 - undefined

Answer 1

首先，使用DFS或BFS遍历具有|V|个顶点和|E|条边的单个连通分量G(V, E)的时间复杂度为O(|V|+|E|)。

以图的顶点和边的数量为基础，时间复杂度为线性。

假设图G(V, E)具有k个连通分量。

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

使用DFS/BFS可以在 O(|Vi|+|Ei|) 的时间复杂度内找到每个组件 Gi。因此，对于每个未访问的顶点，启动一个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|)

- DAle