Working of Kruskal's Algorithm

Board Infinity
Board Infinity
Working of Kruskal's Algorithm

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?


Introduction

We shall talk about Kruskal's algorithm in this article. We shall also see Kruskal's algorithm's difficulty, functionality, example, and implementation in C++ as well. However, we should first comprehend the fundamental concepts, such as spanning tree and least spanning tree, before moving on to the technique.

The least spanning tree for a linked weighted graph is calculated using Kruskal's Algorithm. Finding the subset of edges that will let us pass through each graph vertex is the algorithm's main objective. It utilizes a greedy strategy that looks for the best result at each stage rather than focusing on a global optimum.

Working of Kruskal's Algorithm

Spanning tree - An undirected connected graph's subgraph is a spanning tree.

Minimum Spanning tree - The spanning tree with the lowest total edge weight is known as a minimum spanning tree. The spanning tree's weight is calculated by adding the weights assigned to its edges.

With Kruskal's algorithm, we begin with the edges that have the least weight and keep adding edges until we reach the desired result.

Steps to apply Kruskal's algorithm:

  1. Sort all of the edges first from low weight to high weight.
  2. Add the edge with the lightest weight to the spanning tree at this point. Reject the edge if it would otherwise result in a cycle.
  3. A minimum spanning tree will be ready once all the edges are processed.

Dry Run Example

Let's now use an example to demonstrate how Kruskal's algorithm functions. An illustration will make it simpler to comprehend Kruskal's algorithm. Consider this weighted graph:-

Kruskal's Algorithm

The table below provides the edge weights for the graph above.

Edge

AB

AC

AD

AE

BC

CD

DE

Weight

1

7

10

5

3

4

2

Sort the edges listed above according to ascending weights.

Edge

AB

DE

BC

CD

AE

AC

AD

Weight

1

2

3

4

5

7

10

Let's begin building the smallest spanning tree.

Step 1 - Initialize the MST by adding the edge AB with weight 1.

Kruskal's Algorithm

Step 2 - As it is not producing the cycle, add the edge DE with weight 2 to the MST.

Kruskal's Algorithm

Step 3 - Since the edge BC with weight 3 does not produce a cycle or loop, add it to the MST.

Kruskal's Algorithm


Step 4 - The cycle is not being formed, therefore choose the edge CD with weight 4 to the MST at this time.

Kruskal's Algorithm

Step 5 - Pick the edge AE with weight 5 after that. This edge must be eliminated because including it will start the cycle.

Step 6 - Choose weight 7 and the edge AC. This edge must be eliminated because including it will start the cycle.

Step 7 - Choose AD with a weight of 10. Throwing away this edge will prevent the cycle from starting. As a result, the final minimal spanning tree created using Kruskal's approach from the provided weighted graph is -

Kruskal's Algorithm

The cost of the MST is = AB + DE + CD+ BC = 1 + 2 + 4 + 3 = 10.

The number of vertices in the tree above is now equal to the number of edges, minus 1. The algorithm ends here.

Code

#include <iostream>   
#include <algorithm>   
using namespace std;   
const int MAX = 1e4 + 5;   
int id[MAX], nodes, edges;   
pair <long long, pair<int, int> > p[MAX];   
void init()   
{   
    for(int i = 0;i < MAX;++i)   
        id[i] = i;   
}     
int root(int x)   
{   
    while(id[x] != x)   
    {   
        id[x] = id[id[x]];   
        x = id[x];   
    }   
    return x;   
}     
void union1(int x, int y)   
{   
    int p = root(x);   
    int q = root(y);   
    id[p] = id[q];   
}    
long long kruskal(pair<long long, pair<int, int> > p[])   
{   
    int x, y;   
    long long cost, minimumCost = 0;   
    for(int i = 0;i < edges;++i)   
    {   
        x = p[i].second.first;   
        y = p[i].second.second;   
        cost = p[i].first;   
        if(root(x) != root(y))   
        {   
            minimumCost += cost;   
            union1(x, y);   
        }       
    }   
    return minimumCost;   
}    
int main()   
{   
    int x, y;   
    long long weight, cost, minimumCost;   
    init();   
    cout <<"Enter Nodes and edges";   
    cin >> nodes >> edges;   
    for(int i = 0;i < edges;++i)   
    {   
        cout<<"Enter the value of X, Y and edges";   
    cin >> x >> y >> weight;   
        p[i] = make_pair(weight, make_pair(x, y));   
    }   
    sort(p, p + edges);   
    minimumCost = kruskal(p);   
    cout <<"Minimum cost is "<< minimumCost << endl;   
    return 0;   
}     

write your code here: Coding Playground

Output:

Enter Nodes and edges 57

Enter the value of X, Y, and edges 1 2 1

Enter the value of X, Y, and edges 1 3 7

Enter the value of X, Y, and edges 1 4 10

Enter the value of X, Y, and edges 1 5 5

Enter the value of X, Y, and edges 2 3 3

Enter the value of X, Y, and edges 3 4 4

Enter the value of X, Y, and edges 4 5 2

The minimum cost is 10

Complexity Analysis

The Kruskal algorithm has an O(E logE) or O(V logV) time complexity, where E is the number of edges and V is the number of vertices.

Applications:

  1. Wiring between cities can be laid out using Kruskal's algorithm.
  2. It is possible to use it to install LAN connections.