Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Did you know that the MST (Minimum Spanning Tree) Protocol in networking is designed using a minimum spanning tree algorithm in data structure? The MSTP provides simple yet fully connected routing paths for any bridged local area network. Additionally, it also makes sure that the network loop never gets created in the system. So, in this article, we will learn about the minimum spanning tree in data structures, as well as its functions and applications.

Introduction to Minimum Spanning Tree

The minimum spanning tree algorithm is developed by referencing the field of graph theory in mathematics. Thus, to understand this algorithm, we shall first understand what a spanning tree is? 

A spanning tree of a connected undirected graph is a subgraph, i.e., a tree structure that binds all vertices with a minimum edge cost sum. If you have graph G with vertices V and edges E, then that graph can be represented as G(V, E). For this graph G(V, E), if you construct a tree structure G’(V’, E’) such that the formed tree structure follows constraints mentioned below, then that structure can be called a Spanning Tree. 

  1. V’ = V   (number of Vertices in G’ must be equal to the number of vertices in G)
  2. E’ = |V| - 1   (Edges of G’ must be equal to the number of vertices in graph G minus 1)

Let's create spanning trees for a given graph topology to understand this concept better.

GraphG-Minimum_Spanning_Tree

For the graph above, possible spanning tree structures are:

Spanning_tree_structures

Now, let’s look at the sum of edge weight costs for all these spanning trees represented in the table below: 

Spanning Tree

Sum of Edge Costs

ST - 1 

22

ST - 2

35

ST - 3

36

Table - 1: Sum of Edge costs

The spanning tree structure 1 has an overall edge weight cost of 22. Which is the least possible substructure cost for given graph G. Thus, ST-1 is considered the minimum spanning tree of graph G. A minimum spanning tree in a weighted graph is one that has the least weight of all the other spanning tree structures.

Want a Top Software Development Job? Start Here!

Full Stack Developer - MERN StackExplore Program
Want a Top Software Development Job? Start Here!

How to Find the Minimum Spanning Tree?

The naive method we discussed above is not an ideal approach to find out possible MST structures. In that method, we will have to generate all possible spanning trees at first and then calculate the overall sum of edge weights for each generated spanning tree. After that, we will have to determine the minima of all those spanning trees, which will cost us more time and memory. 

A better method is to locate a vital attribute of the MST, which will provide clarification if some particular edge should be included in it or not. And then, we can use that property to build up the MST gradually. Let’s find out how we can do that with the help of the greedy programming paradigm. The greedy algorithms that we can use are Prim’s Algorithm and Kruskal’s Algorithm. 

First, we shall look into Prim’s algorithm.

1. Prim’s Algorithm

Prim's algorithm begins with a single node and adds up adjacent nodes one by one by discovering all of the connected edges along the way. Edges with the lowest weights that don't generate cycles are chosen for inclusion in the MST structure. As a result, we can claim that Prim's algorithm finds the globally best answer by making locally optimal decisions.

Steps involved in Prim’s algorithms are mentioned below:

  • Step 1: Choose any vertex as a starting vertex.
  • Step 2: Pick an edge connecting any tree vertex and fringe vertex (adjacent vertex to visited vertex) having the minimum edge weight. 
  • Step 3: Add the selected edge to MST only if it doesn't form any closed cycle.
  • Step 4: Keep repeating steps 2 and 3 until the fringe vertices exist.
  • Step 5: End.

Let’s formulate a program to implement an MST using the C programming language.

//Library for accessing the maximum integer variable value

#include <limits.h>

//Library for creating the set

#include <stdbool.h>

#include <stdio.h>

#define Vertices 5

//Finding the vertex with the lowest key value from a set of vertices not included in MST 

int Least_Key(int key[], bool Min_Span_Tree[])

{

    int least = INT_MAX, min_index;

    for (int v = 0; v < Vertices; v++)

        if (Min_Span_Tree[v] == false && key[v] < least)

            least = key[v], min_index = v;

    return min_index;

}

//Utility function to print MST

int print_Prims_MST(int parent[], int graph[Vertices][Vertices])

{

    printf("Edge \tWeight\n");

    for (int i = 1; i < Vertices; i++)

        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);

}

//Function for generating an MST

void prims_MST(int graph[Vertices][Vertices])

{

    int parent[Vertices];

    int key[Vertices];

    bool Min_Span_Tree[Vertices];

    for (int i = 0; i < Vertices; i++)

        key[i] = INT_MAX, Min_Span_Tree[i] = false;

    key[0] = 0;

    parent[0] = -1; 

    for (int count = 0; count < Vertices - 1; count++) {

        int u = Least_Key(key, Min_Span_Tree);

        Min_Span_Tree[u] = true;

        for (int v = 0; v < Vertices; v++)

            if (graph[u][v] && Min_Span_Tree[v] == false && graph[u][v] < key[v])

                parent[v] = u, key[v] = graph[u][v];

    }

    printf("Created Spanning Tree for Given Graph is: \n");

    printf("\n");

    print_Prims_MST(parent, graph);

}

//Driver method

int main()

{

    int graph[Vertices][Vertices] = { { 0, 3, 2, 0, 0 },

                        { 3, 0, 16, 12, 0 },

                        { 2, 16, 0, 0, 5 },

                        { 0, 12, 0, 0, 0 },

                        { 0, 0, 5, 0, 0 } };

    prims_MST(graph);

    return 0;

}

Output:

Implementation-Minimum_Spanning_Tree

You can verify the output of this code by comparing it with ST-1 as the graph that we have passed to this Prim’s algorithm is the same graph G(V, E) represented previously.

2. Kruskal’s Algorithm

Kruskal's approach sorts all the edges in ascending order of edge weights and only adds nodes to the tree if the chosen edge does not form a cycle. It also selects the edge with the lowest cost first and the edge with the highest cost last. As a result, we can say that the Kruskal algorithm makes a locally optimum decision in the hopes of finding the global optimal solution. Hence, this algorithm can also be considered as a Greedy Algorithm.

The steps involved in Kruskal’s algorithm to generate a minimum spanning tree are:

  • Step 1: Sort all edges in increasing order of their edge weights.
  • Step 2: Pick the smallest edge.
  • Step 3: Check if the new edge creates a cycle or loop in a spanning tree.
  • Step 4: If it doesn’t form the cycle, then include that edge in MST. Otherwise, discard it.
  • Step 5: Repeat from step 2 until it includes |V| - 1 edges in MST.

Now, we will develop a C program to implement MST using Kruskal’s algorithm for the graph given below: 

Graph_for_Implementing_Kruskals_Algorithm.

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

//structure for denoting an edge

struct Edge {

int source, destination, weight;

};

//structure for representing a weighted, connected and undirected graph

struct Graph {

int Node, E;

struct Edge* edge;

};

//memory allocation for storing graph with V vertices and E edges

struct Graph* create_Graph(int Node, int E)

{

struct Graph* gph = (struct Graph*)(malloc(sizeof(struct Graph)));

gph->Node = Node;

gph->E = E;

gph->edge = (struct Edge*)malloc(sizeof( struct Edge));

return gph;

}

//Union-Find Subset

struct tree_subset {

int parent;

int rank;

};

//finding the set of selected nodes

int DisjointSet_find(struct tree_subset subsets[], int i)

{

     //find root and make root as parent of i

if (subsets[i].parent != i)

subsets[i].parent

= DisjointSet_find(subsets, subsets[i].parent);

return subsets[i].parent;

}

void DisjointSet_Union(struct tree_subset subsets[], int x, int y)

{

int xroot = DisjointSet_find(subsets, x);

int yroot = DisjointSet_find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

}

//Comparing edges with qsort() in C

int myComp(const void* a, const void* b)

{

struct Edge* a1 = (struct Edge*)a;

struct Edge* b1 = (struct Edge*)b;

return a1->weight > b1->weight;

}

//function for creating MST using Kruskal’s Approach

void MST_Kruskal(struct Graph* gph)

{

int Node = gph->Node;

struct Edge

result[Node]; 

int e = 0; 

int i = 0; 

     //edge sorting

qsort(gph->edge, gph->E, sizeof(gph->edge[0]),

myComp);

     //allocating memory for v subsets

struct tree_subset* subsets

= (struct tree_subset*)malloc(Node * sizeof(struct tree_subset));

for (int v = 0; v < Node; ++v) {

subsets[v].parent = v;

subsets[v].rank = 0;

}

     //V-1 : Path traversal limit

while (e < Node - 1 && i < gph->E) {

struct Edge next_edge = gph->edge[i++];

int x = DisjointSet_find(subsets, next_edge.source);

int y = DisjointSet_find(subsets, next_edge.destination);

if (x != y) {

result[e++] = next_edge;

DisjointSet_Union(subsets, x, y);

}

}

     //prompting state of MST

printf(

"Edges created in MST are as below: \n");

int minimumCost = 0;

     //calculating minimum cost using for loop

for (i = 0; i < e; ++i)

{

printf("%d -- %d == %d\n", result[i].source,

result[i].destination, result[i].weight);

minimumCost += result[i].weight;

}

printf("The Cost for created MST is : %d",minimumCost);

return;

}

//driver function

int main()

{

int Node = 4; 

int E = 6; 

struct Graph* gph = create_Graph(Node, E);

     //graph creation

gph->edge[0].source = 0;

gph->edge[0].destination = 1;

gph->edge[0].weight = 2;

gph->edge[1].source = 0;

gph->edge[1].destination = 2;

gph->edge[1].weight = 4;

gph->edge[2].source = 0;

gph->edge[2].destination = 3;

gph->edge[2].weight = 4;

gph->edge[3].source = 1;

gph->edge[3].destination = 3;

gph->edge[3].weight = 3;

gph->edge[4].source = 2;

gph->edge[4].destination = 3;

gph->edge[4].weight = 1;

gph->edge[5].source = 1;

gph->edge[5].destination = 2;

gph->edge[5].weight = 2;

MST_Kruskal(gph);

return 0;

}

Output:

Kruskals_Implementation-Minimum_Spanning_Tree.

You can verify this output’s accuracy by generating an MST for the graph given above.

Learn From The Best Mentors in the Industry!

Automation Testing Masters ProgramExplore Program
Learn From The Best Mentors in the Industry!

Applications of Minimum Spanning Tree

The following are the applications of minimum spanning tree in data structures:

  • Telecommunication Network Building: A basic naive approach will be more expensive if we develop a telecommunication network for the entire city. Using the MST approach in data structures, we can design a communication system at a much lesser cost. The distinction between Naive and MST routing is illustrated in the diagram below.

Naive_vs_MST-Minimum_Spanning_Tree

  • Constructing Highways or Railroads: The Minimum Spanning Tree (MST) technique is used globally for building roadways or railroads. The MST approach determines the best route between two cities depending on all potential routes. Essentially, the algorithm treats cities as vertices and roads connecting them as edges to produce a subtree that connects two cities with less cost.

Roadway_construction.

Conclusion

In this tutorial, we explored Minimum Spanning Tree (MST) in data structure. We discovered how to create a minimum spanning tree for a given graph topology using Prim’s and Kruskal’s algorithm. Later, in this tutorial, we also learned about minimum spanning trees’ applications to comprehend its significance.

If you are looking for more extensive learning that goes beyond data structures and covers the principles of interactive application development, Simplilearn’s Software Development Courses will prove to be precisely suitable for you. The courses listed in the catalog above will assist you in mastering the craft of software development and prepare you for employment. Explore now and get started!

Have any questions or doubts relating to this article on Minimum Spanning Tree? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!

About the Author

Nikita DuggalNikita Duggal

Nikita Duggal is a passionate digital marketer with a major in English language and literature, a word connoisseur who loves writing about raging technologies, digital marketing, and career conundrums.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.