Minimum Spanning Tree - Prims's Algorithm
Explore Prim's algorithm to understand how it builds a minimum spanning tree by growing it vertex by vertex. This lesson teaches the use of priority queues to select edges with minimum cost, methods to avoid cycles, and implementing the algorithm with practical input examples. You'll gain the ability to apply this greedy strategy to solve graph-based minimum spanning tree problems effectively.
We'll cover the following...
We'll cover the following...
Prim’s algorithm
Prim’s Algorithm also uses the Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal’s Algorithm, we add a vertex to the growing spanning tree in Prim’s Algorithm.
Solution
The algorithm follows the steps listed below:
- Maintain two disjoint sets of vertices: one containing vertices in the growing spanning tree and another that contains vertices not in the growing spanning tree.
- Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using