Minimum Spanning Tree

Description

A minimum spanning tree is

• a tree, meaning it has no cycle
• minimum, meaning it has minimum weight
• spanning, meaning it connects all nodes

The input is an undirected, weighted graph $G$. The output is a tree that

• connects all vertices
• has minimum weight