GraphLab › Minimum spanning tree
A minimum spanning tree (MST) joins all the vertices of a connected, weighted graph using the smallest possible total edge weight, with no cycles. A graph with n vertices has a spanning tree with n − 1 edges.
Sort all edges from lightest to heaviest. Go through them in order and add an edge if it does not form a cycle with the edges already chosen. Stop after n − 1 edges.
Start from one vertex. At each step add the lightest edge that joins the tree to a vertex not yet in it. Stop when every vertex is in the tree.
Kruskal's algorithm runs on the example graph. Choose Min spanning tree (Prim) in the Algorithm menu and tap a start vertex to compare. Edge directions are ignored, and an edge without a weight counts as 1.