CODEWITHSUNDEEP
algorithmperformancedata-structuresgraphtime-complexity
MMMMMCK
MMMMMCK

Reputation: 337

Running Time of Connected Component Count Algorithm

I've been looking into connected components, and came across this description on Wikipedia:

It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

What would be the run time of this operation? I've come across sources that say connected components are done in O(n) time. However, from what I can tell, in the worst case where each vertex is its own connected component, this algorithm will have to perform n DFS/BFS operations, each of which is itself O(n) time. Therefore, shouldn't the run time of this be O(n^2)?

Upvotes: 3

Views: 6432

Answers (1)

DAle
DAle

Reputation: 9117

First, the traversing of a single connected component G(V, E) with |V| vertices and |E| edges using DFS or BFS has O(|V|+|E|) complexity.

linear time (in terms of the numbers of the vertices and edges of the graph)

Let's assume that graph G(V, E) has k connected components. 

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

Every component Gi could be found with DFS/BFS in O(|Vi|+|Ei|). As a result, the total time of the algorithm that for every not visited vertex starts a DFS or BFS to traverse its connected component is:

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

These components have no any common vertex or edge because they are not connected. So: 

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

Finally, the overall complexity of computation of connected components is:

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

Upvotes: 11

Related Questions