= Solution
Run <Kruskal's algorithm> in nonincreasing order of <edge weight>, accepting an <edge> exactly when its endpoints belong to different current <connected components>. Use a <disjoint-set data structure> to test and merge those components. Stop after accepting $|V|-1$ <edges>.
Equivalently, apply ordinary <Kruskal's algorithm> to $w'(e)=-w(e)$. For every <spanning tree>,
$$
\boxed{\sum_{e\in T}w'(e)=-\sum_{e\in T}w(e),}
$$
so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a <maximum spanning tree>. Equal weights may be processed in any fixed order. Sorting dominates the <time complexity>, giving $O(|E|\log |E|+|V|)$ with the usual efficient <disjoint-set data structure>.
Back to article page
