Prim's algorithm is used to find the minimum spanning tree of a graph. In this article, we'll introduce the algorithm and the core concepts, discuss its complexity, then show full code implementations in multiple languages.
Description of Algorithm
This algorithm is a greedy algorithm because it always adds edges with lower weights first. The full code implementation is included in the last section of this article.
Space and Time Complexity
In the table below, e represents the number of edges and v represents the number of vertices.
|Space||We allocate linear extra space for the priority queue and visited nodes set.|
|Time||The priority queue reduces the time of finding minimum weights from O(n) to O(log n), thus, we have log v.|
The full implementation is included below. In some languages, the code also includes additional classes for certain data structures: