An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph

A parallel randomized algorithm for finding the connected components of an undirected graph is presented. The algorithm has an expected running time of T = O(log (n)) with P = O((m + n) / log (n)) processors, where m is the number of edges and n is the number of vertices. The algorithm is optimal in the sense that the product P · T is a linear function of the input size. The algorithm requires $O(m + n)$ space, which is the input size, so it is optimal in space as well.