3

Yes, there are many such algorithms. Two of the easiest are (1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort ...


Only top voted, non community-wiki answers of a minimum length are eligible