 # Prim’s Minimum Spanning Tree Algorithm

The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Earlier, I described the Kruskal’s algorithm to find the MST in time O(E log V). Prim’s algorithm is another greedy algorithm that finds an MST in time O(E log V). The difference is that the Prim’s algorithm grows an MST, starting from a single vertex, always adding the least-cost edge from a tree vertex to a non-tree vertex to the current set of edges in the MST. # Indexed Min-Priority Queue C++ implementation

A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap. # Kruskal’s Minimum Spanning Tree Algorithm

The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.