Prims algorithm

Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a weighted undirected graph.

A minimum spanning tree is a tree that spans all the vertices of the graph with the minimum possible total edge weight.

Outline of Prim’s algorithm:

1. Start with an arbitrary vertex as the starting point.
2. Initialize an empty set to store the MST.
3. Initialize a priority queue (min-heap) to store the edges connected to the current MST.
4. Mark the starting vertex as visited.
5. Add all the edges connected to the starting vertex to the priority queue.
6. Repeat the following steps until all vertices are visited or the priority queue is empty:
   • a. Remove the minimum-weight edge (u, v) from the priority queue.
   • b. If the vertex v is not visited, add it to the MST and mark it as visited.
   • c. Add all the edges connected to v that lead to unvisited vertices to the priority queue.
7. Return the MST.

The pseudocode for Prim’s algorithm:

Prim's Algorithm:
Input: Graph G with vertices V and edges E, weights assigned to each edge

1. Initialize an empty set to store the MST: MST = {}
2. Initialize a priority queue (min-heap) to store the edges connected to the current MST: PQ = {}
3. Select an arbitrary starting vertex s from V.
4. Mark s as visited.
5. Add all the edges connected to s to the priority queue PQ.
6. Repeat the following steps until all vertices are visited or PQ is empty:
   a. Remove the minimum-weight edge (u, v) from PQ.
   b. If v is not visited:
      - Add (u, v) to MST.
      - Mark v as visited.
      - Add all the edges connected to v that lead to unvisited vertices to PQ.
7. Return MST.

Example:

     2       3
(A)------(B)------(C)
 | \      |       /
 |  \5    |    1/
6|   \    |   /
 |    \   |  /
(D)------(E)

     2       3
(A)------(B)------(C)
           |      
           |     
          (E)