A greedy algorithm that finds an MST by growing a tree from a single vertex.
Prim's algorithm is another popular greedy algorithm for finding a Minimum Spanning Tree (MST), but it takes a different approach than Kruskal's. Instead of considering all edges at once, Prim's algorithm grows the MST from a single, arbitrary starting vertex. It works by maintaining two sets of vertices: those already in the growing MST and those not yet included. The algorithm starts with the initial vertex in the MST set. Then, in each step, it identifies the edge with the minimum weight that connects a vertex from the MST set to a vertex outside of it. This minimum-weight edge and its corresponding vertex are then added to the MST set. This process is repeated until all vertices have been included in the MST. To efficiently find the minimum-weight edge at each step, a min-priority queue is used. The priority queue stores the vertices that are not yet in the MST, with their priority being the weight of the cheapest edge connecting them to the MST. With a binary heap, the time complexity of Prim's algorithm is O(E log V). It is generally faster than Kruskal's for dense graphs.