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

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

2. Kruskal's Algorithm:

--->Kruskal'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 Kruskal's Algorithm there is no need of the starting node, it need of the edge setting in an ascending order. 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 Kruskal's Algorithm:

Example:

Solution:

Step 1: In Kruskal's Algorithm firstly we have to arrange the weight of the paths in an ascending order               as follows

                            {1, 2, 2, 4, 4, 6, 7, 7, 8, 8, 9, 10, 11, 14}

Step 2: In next step we will beginning from first element.

              {1}       

       

Step 3: Repeat the step until last element.

             {1,2}

     

             {1,2,2}

       

             {1,2,2,4}

           

             {1,2,2,4,4}

  
           {1,2,2,4,4,7}

   

Note: Here the path weight '7' from 'i' to 'c' makes the loop so we are not taking that path

         {1,2,2,4,4,7,8}

        {1,2,2,4,4,7,8,9}

Example 1: 

                  

Example 2: 

                           

Kruskal's Algorithm:

----> MST_KRUSKAL(G,W)

         A ⋲ ф

         for each vertex V ⋲ V[G]

            do MAKE-SET(V)

        Sort the edge of E into decreasing order by weight W

        for each edge (u, v) ⋲ E , taken in non decreasing order by weight W
         

        do if FIND-SET (u) ≠ FIND-SET (v)

        then A ← A U {u, v}                                        ..........  Here U refers to Union
        Union(u, v)

        return A

Complexity:

                          n log n , or

                          E log V , or

                          V log E