Maximum Spanning Tree

overview

Summary

A maximum spanning tree (Max-ST) connects all vertices of a weighted, undirected graph with the highest possible total edge weight while avoiding cycles. It is the mirror concept of the minimum spanning tree, but maximizes weight instead of minimizing. You can compute it by adapting classic MST algorithms like Kruskal and Prim using descending order or by negating weights. Max-STs are useful on similarity graphs, reliability planning, and clustering where larger weights mean stronger connections.