# 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?

• What do you mean "edges being checked"? I don't understand the problem statement. – quicksort Mar 17 '17 at 16:46
• By "checking an edge" I mean that there is a cost associated to knowing if the edge between two vertices actually exists. – sortega Mar 17 '17 at 17:01
• Do we know all the costs in advance? Is it like "you can pay $c_{uv}$ to see whether $(u, v) \in E$"? Also, how do you score solutions? What is the "lowest possible cost"? The lowest for which you can exhibit a proof certificate? – quicksort Mar 17 '17 at 17:09