Algorithm for finding connected components checking as few edges as possible Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?
You are looking for the minimum spanning tree for each connected component.