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

Question

利用广度优先搜索或深度优先搜索，在线性时间内（根据图的顶点和边的个数）计算图的连通分量是很简单的。在任何一种情况下，从某个特定顶点v开始的搜索都将在返回之前找到包含v（不再包含）的整个连通组件。若要找到图的所有连通分量，请循环遍历图的顶点，每当循环到达以前发现的连通分量中尚未包含的顶点时，就开始新的广度优先或深度优先搜索。

这个操作的运行时间是多少？我遇到过一些消息来源，说连接的组件是在O(n)时间内完成的。然而，据我所知，在最坏的情况下，每个顶点都是它自己的连通分量，这个算法将不得不执行n个DFS/BFS操作，每个操作本身都是O(n)时间。因此，它的运行时不应该是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)

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|)