CLUSTER Algorithm Design: Finding Connected Components

Finding Connected Components

In order to find the connected components in the graph, either Breadth First Search BFS of Depth First Search DFS can be exploited to report the connected components using a stack or a queue respectively. DFS was used in CLUSTER algorithm.

Run time analysis:

The running time of the finding connected components T(n) can be expressed as follows:

T(n) = initialization cost + DFS cost (or BFS) = O(|V|) + O(|V| + |E|) = O(|V| + |E|)