Prim's Algorithm

Graph Theory · Axiom Academy

LESSON Prim's Algorithm for Minimum Spanning Trees Learn how to greedily construct a minimum spanning tree by growing from a starting vertex 1. The Minimum Spanning Tree Problem Given a weighted, connected graph G = (V, E) with n vertices, we want to find a tree that: Uses exactly n - 1 edges (tree property) Has the minimum total edge weight Watch as we visualize a weighted graph and identify which edges should be included in the MST. 2. The Greedy Selection Strategy Prim's algorithm uses a cut-based greedy approach : This strategy ensures we always make the locally optimal choice, which leads to a globally optimal MST. 3. Building the MST Step by Step Let's walk through Prim's algorithm on our example graph: Initialize: Start with any vertex (say A) in the MST Repeat: Find the minimum-weight edge connecting the MST to an outside vertex Add: Include this edge and its endpoint in the MST Continue: Repeat until all vertices are included Watch the tree grow edge by edge! 4. The Growing Tree Perspective Think of Prim's algorithm as growing a tree from a seed (starting vertex): The tree starts with one vertex At each step, the tree "reaches out" to the nearest neighbor The tree expands until it spans all vertices The result is always a minimum spanning tree This visualization shows the MST highlighted in the final graph. The efficiency of Prim's algorithm depends on the data structure used: Array: O(V²) - good for dense graphs

This is the written version of the interactive lesson above. See the full Graph Theory course.