Prim's Algorithm

code data_structures algorithms
Practice Quiz →
Figure: Prim’s algorithm is a greedy method for building a Minimum Spanning Tree (MST)

Prim’s algorithm is a greedy method for building a Minimum Spanning Tree (MST) in a weighted, connected graph. The algorithm starts from any single node and grows a tree outward one edge at a time. At each step, it looks at all edges that connect a visited node to an unvisited node, and it selects the edge with the smallest weight.

Figure: Prim's algorithm uses a Priority Queue

Prim’s algorithm grows a minimum spanning tree by starting at any node and using a priority queue implemented as a binary min-heap to always select the smallest-weight edge that connects the visited set to an unvisited node. At each step, all eligible edges from the newly added node are inserted into the heap, and the algorithm repeatedly pops the minimum edge from the top of the heap, adds the corresponding node to the tree, and continues until all nodes are included.

💬 Click on the content to Ask AI
graph_algorithm greedy_algorithm mst combinatorial_optimization deterministic_algorithm undirected_graph weighted_graph