Using Kruskal’s Algorithm How to find Minimum Spanning Tree?

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, undirected and weighted graph that connects all the vertices with the minimum possible total edge weight. It is a spanning tree whose sum of edge weights is as tiny as possible.

There are many applications for minimum spanning trees. For example, in the design of computer networks, a minimum spanning tree can be used to find the least expensive way to connect all of the nodes in the network. In this context, the edges in the minimum spanning tree represent the optimal connection path between the nodes. Another application is in the analysis of geographic data, where a minimum spanning tree can be used to find the set of edges that define the boundary of a region.

What is a spanning tree?

A spanning tree is a subset of a graph that includes all of the vertices and some of the edges of the graph. A spanning tree must be a connected graph with no cycles. The edges of the spanning tree are called branches.

Spanning trees are used in a variety of applications, including network design, computer science, and electrical engineering. In network design, a spanning tree is often used to find the least expensive way to connect a set of computers. In computer science, spanning trees are used to create data structures, such as search trees. In electrical engineering, they are used to design circuits.

The name “spanning tree” comes from the fact that a spanning tree must span (or touch) all of the vertices of the graph.

Difference between Minimum spanning tree and spanning tree:

Spanning TreeMinimum Spanning Tree
A spanning tree is a subset of the edges of a connected, undirected graph that connect all the vertices together.A minimum spanning tree is then a spanning tree with the minimum possible total edge weight.
A spanning tree may not necessarily have the least possible total edge weight.A minimum spanning tree has the least possible total edge weight.
Spanning tree vs minimum spanning tree

Now, there are actually two algorithms present to solve the minimum spanning tree.

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

Both algorithms have their own way to solve this problem and there are some differences between Prim’s Algorithm and Kruskal’s Algorithm. For this article, we’ll only focus on Kruskal’s Algo.

Kruskal’s Algorithm for MST:

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. It works by first sorting the edges of the graph by weight from smallest to largest and then selecting the edges in order, adding them to the spanning tree until all vertices are included.

The time complexity of Kruskal’s algorithm is O(E log E), where E is the number of edges in the graph. This is because the algorithm sorts the edges by weight before selecting them.

Kruskal’s algorithm is used in many applications, such as finding the minimum cost to connect a set of computers or finding the shortest path between two cities.


The process of Kruskal’s algorithm is as follows:

  1. Sort the edges by weight from smallest to largest
  2. Start with an empty tree
  3. Add the edges to the tree one at a time, in order of weight
  4. If adding an edge would create a cycle, do not add it
  5. Continue until all vertices have been added to the tree

For example, let’s try to solve this graph.

Solution:

Let’s try to solve this solution step by step.

Sort the edges by weight from smallest to largest:

To sort the edges, let’s first take the matrix

v1v2v3v4v5
v102003
v220108
v301054
v400506
v538460

Now, from this matrix, we get two major things.

  1. We’ve a sorted array for the edges, i.e. [e3(1), e2(2), e1(3), e6(4), e4(5), e5(6), e7(8)].
  2. which two vertices are connected with that edge.

Now, what’s next?

See this video below👉

I hope you’ve understood the video.

In this video, you can see that for e6(4) we are getting a loop. But we can not include a loop so we removed that edge from our final MST. But we’ve done that easily because we can clearly see that. But how our code can understand when it is creating a loop?

For this, we’ve another algorithm, which is the Union-Find Algorithm.

The union-find algorithm is a way to keep track of the connectedness of a set of elements. It allows for quick determination of whether two elements are in the same set or belong to another set(disjoint set), and also for quick determination of which set a given element is in.

The algorithm is based on the idea of keeping track of the “roots” of sets. If two elements are in the same set, then they will have the same root. To find out if two elements are in the same set, we just need to check if they have the same root. To find the root of an element, we start at the element and follow its “parent” link until we reach an element that has no parent (i.e., is the root of the set).

The heart of the algorithm is the union operation, which combines two sets into one. To union two sets, we just need to choose one of the elements to be the new root, and then update the parent links of all the elements in the other set to point to the new root.

Here we’ve been introduced to another term, i.e. Disjoint set.

What is A Disjoint Set?

A disjoint set is a collection of sets that have no elements in common. For example, the set of all even numbers and the set of all odd numbers are disjoint sets.

So finally we get our Minimum Spanning tree👉👉

Code:

//MST using Kruskal's Algorithm
#include <stdio.h>
#include <stdlib.h>
#define VAL 999 //It sets the infinites as 999
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
// union - find : Union-Find helps us to find if there is any loop present in the mst
int find(int i)
{
    while (parent[i])
        i = parent[i];
    return i;
}
int uni(int i, int j)
{
    if (i != j)
    {
        parent[j] = i;
        return 1;
    }
    return 0;
}
int main(void)
{
    printf("Enter the no. of vertices:");
    scanf("%d", &n);
    printf("Enter the cost adjacency matrix:\n");
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &cost[i][j]);
            if (cost[i][j] == 0)
                cost[i][j] = VAL;
        }
    }
    printf("The edges of Minimum Cost Spanning Tree are\n");
    while (ne < n)
    {
        for (i = 1, min = VAL; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (cost[i][j] < min)
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = find(u);
        v = find(v);
        if (uni(u, v))
        {
            // printing edges
            printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
            mincost += min;
        }
        cost[a][b] = cost[b][a] = 999;
    }
    // minimum cost
    printf("\nMinimum cost = %d\n", mincost);
}

Input:

Enter the no. of vertices:5
Enter the cost adjacency matrix:
0 2 0 0 3 2 0 1 0 8 0 1 0 5 4 0 0 5 0 6 3 8 4 6 0 /Put these inputs in your terminal one by one/

Output:

The edges of Minimum Cost Spanning Tree are
1 edge (2,3) =1
2 edge (1,2) =2
3 edge (1,5) =3
4 edge (3,4) =5
Minimum cost = 11

Snehasish Konger
Snehasish Konger

Hey, I'm Snehasish Konger, the guy behind this website.
Read my blogs from here-

Articles: 112

Leave a Reply

Your email address will not be published.

You cannot copy content of this page