Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Prim’s Algorithm
2.1.
Pseudocode 
2.2.
Example
2.3.
Solution 
3.
Kruskal’s Algorithm
3.1.
Pseudocode
3.2.
Example 
3.3.
Solution
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Spanning Tree

Author Teesha Goyal
2 upvotes
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

A spanning tree is a minimal graph that is connected, acyclic and undirected. It has all the vertices from the corresponding graph but has a subset of edges. A graph can have many spanning trees.

The edges of the graph are assigned a value called the weight of the edge and a spanning tree is made up of a subset of edges that connects all the vertices with minimum total weight is called a Minimum Spanning Tree.

In a minimum spanning tree, every pair of nodes is connected by a unique path, and in such a tree, if there are n vertices, then there must be n-1 number of edges. If we add any new edge without adding a new vertex, that will create a cycle.

Fig 1.  A connected cyclic graph

   Fig 2. Minimum spanning tree of the above graph

As shown in the above figure, Fig 1(a) is the image of a weighted graph that is connected and cyclic, and Fig 1(b) is the minimum spanning tree for the graph mentioned above.

Following are the two algorithms to find a minimum spanning tree for a given graph:

  1. Prim’s algorithm 
  2. Kruskal’s Algorithm


We will discuss both the algorithms in detail now.

Prim’s Algorithm

Prim’s algorithm is also known as Jarnik’s algorithm. It is a greedy approach to find the minimum spanning tree containing all the vertices and a subset of edges whose total weight is minimum for a weighted undirected cyclic graph. It works on the principle of going with the best next move. It works well with denser graphs.

The steps of Prim’s algorithm are:

  • Initialize the visited vector for all vertex as False, Nbr vector as -1 and Dictance as infinity or a very large number.
     
  • Firstly, take anyone vertex at random from the graph say 1 and initialize the required minimum spanning tree with that vertex by adding it to tree_edge and set visited of that vertex as True.
     
  • Search for the neighbours j of vertex 1 and set Nbr[j]  as 1 and distance[j] as the weight of edge (1, j).
     
  • For all the remaining vertices, select and add the vertex i with visited[i] as False and distance[i] is minimum.
     
  • Keep on updating the distance of vertex on addition of any edge in the tree with the updated minimum distance.
     
  • Continue the previous 2 steps until all the vertices are added to our minimum spanning tree.

Pseudocode 

Function Prim
    // Inintialize important vectors
    for i = 1 to n      //n is the number of vertices
        visited[i] = False
        Nbr[i] = -1
        Distance[i] = infinity

    tree_edges = []   // to store the edges considered in our minimum spanning tree
    visited[1] = True  //source - 1
    for each edge (1,j)
        Nbr[j] = 1
        Distance[j] = weigth(1,j)

    //for remaining vertices
    for i =2 to n
        choose u such that visited[u] = False
        and distance[u] is minimum
        visited[u] = True
        tree_edge.append{(u,Nbr[u])}   //add the edge

        //updating the distance due to the addition of u vertex
        for each edge (u,v) with visited[v] = False
            if Distance[v] > weight(u,v)
                Distance[v] = weigth(u,v)
                Nbr[v] = u

Example

For the below-given graph, we have to find the minimum spanning tree.

Fig 3. A graph to find the minimum spanning tree.

Solution 

Step1: First of all, we take any vertex at random, say A. We initialize our minimum spanning tree with vertex A.

Step2: Now, all the edges of A, the one with minimum weight, is with E, i.e.1. So we add this edge to our tree. 

Step3: Now, for all the edges of A and E that is EF, EB, AD and AB, the one with the minimum weight is AB. So, we add AB to our tree.

Step4: Now again repeat the same process; we get BD 

Step5: Repeating the same process of finding the minimum weighted edge that introduces a new vertex. We get DC.

Step6: Now Bc is the edge with minimum weight, but it does not introduce any new vertex to our minimum spanning tree; hence we move on to the following minimum weight edge that is EF and hence F is a new vertex we add this edge.

We stop now as all the vertices are added to the graph, and adding any more edge will create a cycle in our tree. So, this is our required minimum spanning tree using Prim’s algorithm. And the total weight is 1+2+2+1+5 = 12.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Kruskal’s Algorithm

Kruskal’s Algorithm is also a greedy approach to find the minimum spanning tree of an undirected connected cyclic graph. In this algorithm, we find the minimum weighted edges from the set of all the edges. 

The steps of Kruskal’s algorithm are:

  • We take the edge with the minimum weight and initialize our minimum spanning tree.
     
  • Continue to select the edge with the minimum weight that either connects our minimum spanning tree or introduces a new vertex. To avoid the formation of cycles, we will use a components vector that will give us the component number for any vertex already considered. So, if (u,v) is an edge we want to check for a cycle, then we can check if component[u] is equal to component[v]; if equal, then it forms a cycle.
     
  • Continue adding the edge until all the vertices are added to our minimum spanning tree and the tree is connected.

Pseudocode

Function Kruskal
    Let E = [e1, e2, e3,......en] be edges sorted by weights

    for j = 1 to n
        component[j] = j  //to avoid taking edges that make a cycle
        //an edge (u,v) forms an edge if component[u] == component[v]

        tree_edge = []
        i = 1

        while(tree_edge.length() < n-1)   //after this adding any edge will make a cycle
            let E[i] = (u,v)
            if component[u] != component[v]
                tree_edge.append(E[i])

                for j = 1 to n
                    if component[j] == component[v]
                        component[j] = component[u]

Example 

For the below-given graph, we have to find the minimum spanning tree using Kruskal's algorithm.

Solution

Step1: First, we find the edge with minimum weight now; since AE and DC both have the minimum weight of 1, we can select any one of these. Let’s say AE.

Step2: Now, we select DC as the next edge as it has the least weight, and it also introduces two new vertices, D and C.

Step3: Now we have two edges AB and BD both have the least weight of 2 units, and both introduce a new vertex so we can take anyone say AB.

Step4: Now, the least weight edge is BD, and it does not introduce an edge but connects the two trees, so we add this edge.

Step5: Now the least weight edge is BC; both create a cycle, so we skip it and move on to the next least weighted edge, EF because it introduces the vertex F.

Step6: We stop now as all the vertices are added, and adding any more vertex will create a cycle. 

FAQs

1. What is tree data structure?
A tree is a data structure where the elements are not arranged in hierarchical order. It is an acyclic graph with nodes and edges.

2. What is a Spanning Tree?
A spanning tree is a minimal graph that is connected, acyclic and undirected. It has all the vertices from the corresponding graph but has a subset of edges. A graph can have many spanning trees.

3. What is a minimum spanning tree?
The edges of the graph are assigned a value called the weight of the edge, and a spanning tree is made up of a subset of edges that connects all the vertices with minimum total weight is called a Minimum Spanning Tree.

4. What is Prim’s Algorithm?
Prim’s Algorithm is a greedy approach to find a minimum spanning tree for a given connected undirected cyclic graph.

5. What is the most significant difference between Prim’s and Kruskal’s algorithms?
Prim’s algorithm always has a connected graph even in the intermediate stages, but in Kruskal's algorithm, we may have some intermediate stages where the graph is not connected.

Key Takeaways

In this article, we learned what is spanning and minimum spanning trees, and we also learned two algorithms to find the minimum spanning tree for a given graph, namely Prim’s and Kruskal’s algorithms.
Check out this problem - No of Spanning Trees in a Graph

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Live masterclass