Q15Discrete Mathematics

In computational graph theory, Prim's Algorithm is a highly powerful, greedy mathematical algorithm utilized to definitively compute the Minimum Spanning Tree (MST) of a connected, undirected graph possessing weighted edges. While Kruskal's Algorithm (another MST solver) focuses globally on sorting edges and merging disparate forests, Prim's Algorithm operates locally. It begins with a single, isolated vertex and meticulously, continuously expands a single growing tree outwards, edge by edge, until it has successfully engulfed every single vertex in the entire graph.

Algorithmic Methodology

Prim's algorithm strictly maintains two distinct sets of vertices during its execution: a set $V_{tree}$ containing vertices already incorporated into the growing MST, and a set $V_{remaining}$ containing vertices yet to be visited.

• Step 1: Initialization. The algorithm mathematically selects any arbitrary starting vertex from the graph. It immediately adds this single vertex to the $V_{tree}$ set. The $V_{tree}$ set now contains exactly one node, and the $V_{remaining}$ set contains all others.
• Step 2: Boundary Evaluation. The algorithm aggressively scans the mathematical boundary of the growing tree. It analyzes every single edge that physically connects a vertex currently inside $V_{tree}$ to a vertex currently residing outside in $V_{remaining}$.
• Step 3: Greedy Selection. From this boundary set of connecting edges, the algorithm executes its greedy heuristic: it identifies and selects the single edge possessing the absolute lowest (minimum) weight. If multiple edges tie for the minimum weight, any one of them can be arbitrarily chosen.
• Step 4: Tree Expansion. The algorithm officially adds this minimum-weight edge to the Minimum Spanning Tree structure. Crucially, the external vertex connected by this edge is permanently removed from the $V_{remaining}$ set and officially absorbed into the $V_{tree}$ set.
• Step 5: Iteration and Termination. The algorithm aggressively loops, repeating Steps 2, 3, and 4. With each iteration, the $V_{tree}$ set grows larger, and the boundary of connecting edges changes. The algorithm halts instantly when the $V_{remaining}$ set is completely empty, meaning the $V_{tree}$ set now contains every single vertex in the graph, successfully completing the MST.

Algorithmic Advantages

Because Prim's algorithm always expands outwards from a single connected component, it never mathematically requires complex cycle-detection data structures (like Disjoint-Sets). By definition, connecting to a vertex in $V_{remaining}$ cannot form a cycle. It performs exceptionally well on dense graphs (graphs with many edges) when implemented with efficient Min-Priority Queues (Heaps).