---

Prims Algorithm

---

• The Prim’s algorithm makes a nature choice of the cut in each iteration – it grows a single tree and adds a light edge in each iteration.
• Prim’s algorithm is a greedy algorithm that is used to form a minimum spanning tree for a connected weighted undirected graph.
• In other words, the algorithm builds a tree that includes every vertex and a subset of the edges in such a way that the total weight of all the edgesin the tree is minimized.

Algorithm

Step 1: Select a starting vertex 
Step 2: Repeat Steps 3 and 4 until there are fringe vertices 
Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight 
Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] 
Step 5: EXIT

Explanation

• Choose a starting vertex.
• Branch out from the starting vertex and during each iteration, select a new vertex and an edge. Basically, during each iteration of the algorithm, we have to select a vertex from the fringe vertices in such a way that the edge connecting the tree vertex and the new vertex has the minimum weight assigned to it.
• The running time of Prim’s algorithm can be given as O(E log V) where E is the number of edges and V is the number of vertices in the graph.

---