Computer Science

What is Minimum Spanning Tree? | Algorithms

Author: Zeba Ali

• Table of Contents :
  • Minimum Spanning Tree
  • Kruskal’s Algorithm
  • Prim’s Algorithm

Before knowing about the Minimum Spanning Tree , We must know about spanning tree.

A Spanning Tree is a connected undirected graph, a spanning tree is a sub graph that is a tree and joined all vertices. A single graph can have many spanning trees.

Example:-

Minimum Spanning Tree

Minimum spanning tree is a spanning tree which has minimum total cost.

How to calculate minimum cost spanning tree?

We can calculate it by using two algorithms:-

• Prim’s Algorithm
• Kruskal Algorithm

Kruskal’s Algorithm

It is a Greedy Algorithm. The Greedy Choice is to put the smallest weight edge first that does not form a cycle in the MST constructed so far.

Find the Minimum Spanning Tree of the following graph using Kruskal’s algorithm

here are 9 vertices and 12 edges. So MST formed (9-1) = 8 edges

Step1: So, first take (h, g) edge

Step -2: then (g, f) edge.

Step-3: then (a, b) and (i, g) edges are considered, and the forest becomes

Step 4: Now, edge (h, i). Both h and i vertices are in the same set. Thus it creates a cycle. So this edge is discarded.

        Then edge (c, d), (b, c), (a, h), (d, e), (e, f) are considered, and the forest becomes.

Step 5: In (e, f) edge both endpoints e and f exist in the same tree so discarded this edge. Then (b, h) edge, it also creates a cycle.

Step 6: After that edge (d, f) and the final spanning tree is shown as in dark lines.

Step 7: This step will be required Minimum Spanning Tree because it contains all the 9 vertices and (9 – 1) = 8 edges

1. e → f,  b → h,  d → f [cycle will be formed]  

Minimum Cost MST

Prim’s Algorithm

It is a greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices:

• Contain vertices already included in MST.
• Contain vertices not yet included.

Find the minimum cost spanning tree for the following graph using Prim’s algorithm.

In Prim’s algorithm, first we initialize the priority Queue Q. to contain all the vertices and the key of each vertex to ∞ except for the root, whose key is set to 0. Suppose 0 vertex is the root, i.e., r. By EXTRACT – MIN (Q) procure, now u = r and Adj [u] = {5, 1}.Prime Ministers of India | List of Prime Minister of India (1947-2020)

Removing u from set Q and adds it to set V – Q of vertices in the tree. Now, update the key and π fields of every vertex v adjacent to u but not in a tree.

1. Taking 0 as starting vertex  
2.   Root = 0  
3.     Adj [0] = 5, 1  
4.   Parent, π [5] = 0 and π [1] = 0  
5.       Key [5] = ∞ and key [1] = ∞  
6.   w [0, 5) = 10  and w (0,1) = 28  
7.    w (u, v) < key [5] , w (u, v) < key [1]  
8.         Key [5] = 10 and key [1] = 28  
9. So update key value of 5 and 1 is:  

Now by EXTRACT_MIN (Q) Removes 5 because key [5] = 10 which is minimum so u = 5.

1. Adj [5] = {0, 4} and 0 is already in heap  
2. Taking 4, key [4] = ∞      π [4] = 5  
3. (u, v) < key [v] then key [4] = 25  
4. w (5,4) = 25  
5. w (5,4) < key [4]  
6. date key value and parent of 4.  

Now remove 4 because key [4] = 25 which is minimum, so u =4

1. Adj [4] = {6, 3}  
2. Key [3] = ∞         key [6] = ∞  
3. w(4,3) = 22        w (4,6) = 24  
4. w (u, v) < key [v]    w (u, v) < key [v]  
5. w (4,3) < key [3]      w (4,6) < key [6]  

Update key value of key [3] as 22 and key [6] as 24.

And the parent of 3, 6 as 4.

1. π[3]= 4       π[6]= 4   

1. u = EXTRACT_MIN (3, 6)            [key [3] < key [6]]  
2. u = 3              i.e.  22 < 24  

Now remove 3 because key [3] = 22 is minimum so u =3.

1. Adj [3] = {4, 6, 2}  
2.   4 is already in heap  
3.   4 ≠ Q key [6] = 24 now becomes key [6] = 18  
4.   Key [2] = ∞            key [6] = 24  
5.   w (3, 2) = 12          w (3, 6) = 18  
6.   w (3, 2) < key [2]         w (3, 6) < key [6]  

Now in Q, key [2] = 12, key [6] = 18, key [1] = 28 and parent of 2 and 6 is 3.

1. π [2] = 3      π[6]=3  

Now by EXTRACT_MIN (Q) Removes 2, because key [2] = 12 is minimum.

1. u = EXTRACT_MIN (2, 6)  
2. u = 2          [key [2] < key [6]]  
3.         12 < 18  
4. Now the root is 2   
5. Adj [2] = {3, 1}  
6.    3 is already in a heap  
7. Taking 1, key [1] = 28  
8.    w (2,1) = 16  
9.    w (2,1) < key [1]  

So update key value of key [1] as 16 and its parent as 2.

1. π[1]= 2  

Now by EXTRACT_MIN (Q) Removes 1 because key [1] = 16 is minimum.

1. Adj [1] = {0, 6, 2}  
2.     0 and 2 are already in heap.  
3. Taking 6, key [6] = 18  
4.    w [1, 6] = 14  
5.    w [1, 6] < key [6]  

Update key value of 6 as 14 and its parent as 1.

1. Π [6] = 1  

Now all the vertices have been spanned, Using above the table we get Minimum Spanning Tree.

1. 0 → 5 → 4 → 3 → 2 → 1 → 6  
2. [Because Π [5] = 0, Π [4] = 5, Π [3] = 4, Π [2] = 3, Π [1] =2, Π [6] =1]  

Thus the final spanning Tree is

Total Cost = 10 + 25 + 22 + 12 + 16 + 14 = 99

Read Similar Articles :

Programme to Count the Word in a Text File | C++

For any Query

Mail us at edumoundofficial@gmail.com

This write-up was edited by Tanya.