What is Minimum Spanning tree in DAA | Its Types | Prim's Algorithm.....

What is Minimum Spanning tree in DAA | Its Types , Algorithms...

                           

What is Minimum Spanning tree in DAA ?

--->In this Blog we will understand "What is Minimum Spanning Tree and its types" where we discuss all about its types and its algorithm.

---->A Minimum Spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight. It is a way of finding the most economical way to connect a set of vertices. 

---->A minimum spanning tree is not necessarily unique. All the weights of the edges in the MST must be distinct. If all the weights of the edges in the graph are the same, then any spanning tree of the graph is an MST. The edges of the minimum spanning tree can be found using the greedy algorithm or the more sophisticated Kruskal or Prim's algorithm.

Types of Minimum Spanning Tree

1. Prim's Algorithm:

-----> Prim's Algorithm comes under the  Minimum spanning tree which uses the greedy Approach. Where it has the steps or the rules for the algorithm to work. 

----->In Prim's Algorithm there is need of the starting node. It also include the queue format, as the name suggest the tree means it follows the tree format for the final key or the answers.

----->This Algorithm also have the graph figure and get arranged in tree format at last where it is acyclic in nature.

Steps of Prim's Algorithm:

Example: 

                                     

 

Step 1: Take any node From where you are going to start as shown following.

              "In this case we start from node 'a'."

      

Step 2: Making the queue in parallel as it has the path weight in the queue.

      
                                   Queue = {4 , 8}

Step 3: We need to choose the minimum path as it is minimum spanning tree so there is need of the                      shortest weight path.

              In this case the short path/root is "4".

                    

                                 Queue = {8, }

Step 4: Repeating the step 2 and 3 for all we get as follows

         

                                  Queue = {8, 8, 11}

             

                                  Queue = {8, 11}

             

                                   Queue = {8, 11, 2, 7, 4}

  

                           
     

                             Queue = {8, 11, 7, 4}

        

                             Queue = {8, 11, 7, 4, 7, 6}             ------> From this we choose "4" because it is                                                                                                        small in compare to the other element in                                                                                                  the queue.

         
                           Queue = {8, 11, 7, 7, 6}

       
                        Queue = {8, 11, 7, 7, 6, 2, 14, 10}

         
                       Queue = {8, 11, 7, 7, 6, 14, 10}

       

                     Queue = {8, 11, 7, 7, 6, 14, 10, 1}

            

                   Queue = {8, 11, 7, 7, 6, 14, 10}

Note: In node "g" there is also the extension of the path by '6' and '1', we take the path '1' then in the queue there is also a small number which is '6' , due to loop maker we cannot take that path.

             

Note: There is an 3 path coming from node "h" that is '8', '7' , '11' this paths get in the loop form so we do not take that path which make a cyclic graph. 

           

                 Queue = {8, 11, 7, 6, 14, 10}

         
                Queue = {8, 11, 7, 6, 14, 10, 9}

         
                Queue = {8, 11, 7, 6, 14, 10}

      

 Example 1: 

Prim's Algorithm:

-------> MST_PRIM(G,W,R)

             for each U Є V[G]

             do key[U] ← ∞

        П[U] ← nil

             key[R] ← 0

             Q ← V[G]

              

            While Q ≠ ф

            do U ← EXTRA-MIN(Q)

             for each  V Є adj[U]

             

            do if V Є Q and W(U,V) < key[V]

               then П[V] ← U

               key[V] ←W(U,V)

                                                                   ........To be continued............