Efficient algorithm for finding weakly connected components

Question

We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to search a bit to actually find the term).

The most obvious solution would be to do a BFS or DFS on all unvisited nodes and the number of connected components would be the number of searches needed. This is actually what Wikipedia suggests for weakly connected components, too.

My question is if there is a known algorithm that can find these components faster? Or is the BFS/DFS version fast enough (not sure exactly what for)?

Answer 1

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$. Now use any standard algorithm for finding connected components in the resulting undirected graph.

One standard approach for finding connected components is to use DFS. This runs in linear time, i.e., $O(|V|+|E|)$ time.

You can't hope for any algorithm that will perform asymptotically faster: any correct algorithm will have to examine every vertex and every edge at least once, so will have to take at least $\Theta(|V|+|E|)$ time.