GraphLab

Graph theory & algorithm visualizer
About Minimum spanning tree

GraphLab › Minimum spanning tree

Minimum Spanning Tree Visualizer: Kruskal's and Prim's Algorithm

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.

Kruskal's algorithm

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.

Prim's algorithm

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.

Try it in GraphLab

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.

More topics