Prim’s Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

It effectively picks an arbitrary node in the tree, then it will pick the edge with the smallest weight, and continue until a spanning tree is made.

Time Complexity

Prim’s time complexity is dependent on the graph implementation. A search using Prim’s on a graph implemented using an adjacency matrix is O(V^2). Using a binary heap, it is O(E log(V))