Prim Minimum Spanning Tree Greedy Algorithm

Like Kruskal's algorithm, Prim's algorithm is a greedy one. It starts with an empty spanning tree. The idea is to keep two sets of vertices. The first set contains vertices already included in the MST, the other set contains vertices not yet included. At each step, it considers all edges connecting the two sets and chooses the edge with the least weight among them. After selecting an edge, move the other endpoint of the edge to the set containing the MST.
 

A group of edges connecting two sets of vertices in a graph is called a cut in graph theory. So, at each step of the Prim algorithm, we find a cut (in both sets, one contains the vertices already included in the MST, the other contains the remaining vertices), select the least weighted edge from the cut, and contain: This vertex in the MST set (a set containing already included vertices).

How does Prim's algorithm work?
 

The basic idea behind the Prim algorithm is simple. Spanning tree means that all vertices must be connected. Thus, two separate subsets of vertices (discussed above) must be joined to form a spanning tree. And they have to be connected by least weighted edges to make a minimum spanning tree.

Algorithm->
 

1) Create an mstSet that tracks the vertices already contained in the MST.
2) Assign key values ??to all vertices of the input graph. Initialize all key values ??to INFINITE. Assign a key value of 0 to the first vertex so that the first vertex is selected first.
3)while mstSet does not contain all vertices.

   a) Select the vertex u that is not in the mstSet and has the minimum key value.
   b) Include u in mstSet.
   c) update the key value of all adjacent vertices u. To update the key value, iterate over all adjacent vertices. For each neighboring vertex v, if the weight of the edge u-v is less than the previous key value v, we update the key value to the weight u-v
. The idea behind using key values ??is to choose the least weighted edge. in cut. Key values ??are only used for vertices not already included in the MST, and key values ??for these vertices specify the minimum weight of edges connecting to the set of vertices included in the MST.

Example->

The mstSet is initially empty and the vertices are assigned keys {0, INF, INF, INF, INF, INF, INF, INF}. Here INF means infinity. Now select the vertices with the minimum key value. Vertex 0 is selected and included in the mstSet. So mstSet will be {0}. When included in an mstSet, it updates the key values ??of adjacent vertices. Adjacent vertices 0 are 1 and 7. Key values ??1 and 7 are updated to 4 and 8. The following subgraph shows the vertices and their key values, showing only those vertices with finite key values. Vertices included in the MST are shown in green.

Select vertices not already included in MST (not included in mstSET) as the minimum key value. Vertex 1 is selected and added to the mstSet. So mstSet will now be {0, 1}. Update the key value of adjacent vertex 1. Vertex 2 will have a key value of 8.

Select vertices not already included in MST (not included in mstSET) as the minimum key value. You can choose either node 7 or node 2, and node 7 will be selected. So mstSet will now be {0, 1, 7}. Update the key values ??of adjacent vertices 7. The key values ??of vertices 6 and 8 are final (1 and 7 respectively).

Select vertices not already included in MST (not included in mstSET) as the minimum key value. Vertex 6 is selected, so the mstSet is now {0, 1, 7, 6}. Update key value of adjacent vertex 6. The key values ??of vertices 5 and 8 are updated.

Repeat the above steps until the mstSet contains all the vertices of the given graph. As a result, we get the following graph:

How to implement the algorithm described above?

mstSet[] Uses a boolean array to represent the set of vertices contained in the MST. If mstSet[v] is true, v is included in the MST, otherwise it is not included. The key[] array is used to store the key values ??of all vertices. Another parent[] array that holds the parent node index in MST. The parent array is the output array used to display the built MST.

The time complexity of the above program is O(V^2).