• Articles
  • Tutorials
  • Interview Questions
  • Webinars

Kruskal’s Algorithm in DAA: Steps and Implementation

Kruskal’s Algorithm in DAA: Steps and Implementation

Kruskal’s algorithm carefully identifies the most cost-effective route to connect all the cities, minimizing the overall construction cost. In this blog, we will get insights into how Kruskal’s algorithm works, along with its practical implementation and applications.

Table of Contents:

Learn Data Structures and Algorithms in this comprehensive video course:

Introduction to Kruskal’s Algorithm in DAA

Kruskal’s Algorithm in Design and Analysis of Algorithms (DAA) is a fundamental greedy algorithm designed to find the Minimum Spanning Tree (MST) of a connected, undirected graph. Its primary purpose is to identify the subset of edges that connects all vertices in the graph with the minimum possible total weight. The algorithm achieves this by iteratively selecting the smallest available edge that connects two disjoint sets of vertices, avoiding the creation of cycles.

Kruskal’s Algorithm addresses the fundamental concept of a spanning tree in a connected, undirected graph.

Interested in becoming a Full Stack Developer? Take our Full Stack Development Course to take your first step.

Spanning Tree

A spanning tree of a connected, undirected graph is a subgraph that includes all the vertices of the original graph, forming a tree without any cycles. In other words, it is a tree that spans the entire set of vertices, ensuring that there is exactly one path between any two vertices. Spanning trees are crucial in network design and optimization problems as they represent a simplified, acyclic connectivity structure. 

Get 100% Hike!

Master Most in Demand Skills Now !

Minimum Spanning Tree

A minimum spanning tree (MST) is a fundamental concept in graph theory, representing the smallest possible connected subgraph of a given, connected, and undirected graph that spans all its vertices. The “spanning” aspect ensures that all vertices are included, while the “tree” structure ensures connectivity without forming cycles. 

The key characteristic of an MST is that the total weight or cost of its edges is minimized among all possible spanning trees of the original graph. Kruskal’s Algorithm is widely used in various applications, including network design, circuit layout, and transportation planning. Its significance comes from its capacity to offer an effective and methodical strategy for lowering the total cost or weight. The algorithm’s versatility and guaranteed optimality make it a key tool in the field of Design and Analysis of Algorithms.

Spanning and Minimum Spanning Tree

How Does Kruskal’s Algorithm Work

Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree (MST) of a graph. The graph’s MST is a subset of its edges that joins all of its vertices with the least amount of overall weight.

The steps of Kruskal’s algorithm are as follows:

How Does Kruskal's Algorithm Work

Step 1: Sorting of Edges

Arrange all the edges of the graph in ascending order based on their weights.

Step 2: Initialize Disjoint Sets

Create a disjoint set for each vertex in the graph. Initially, each set contains only one vertex.

Step 3: Process Edges

  1. Iterate through the sorted edges.
  2. For each edge, check whether the vertices at its ends belong to the same disjoint set. If they do not, adding the edge won’t create a cycle.
  3. If the vertices are in different sets, add the edge to the minimum spanning tree (MST) and merge the disjoint sets of the two vertices.

Step 4: Termination

Continue this process until the MST has n−1 edges, where n is the number of vertices in the graph.

Want a comprehensive list of interview questions? Here are the Full Stack developer interview questions!

Example

Here is a graphical illustration of the workings of Kruskal’s Algorithm:

step 1 of working of Kruskual Algorithm
step 2 of working of Kruskual Algorithm
step 3 of working of Kruskual Algorithm
step 5 of working of Kruskual Algorithm

Practical Implementation of Kruskal’s Algorithm 

Below is a simple implementation of Kruskal’s Algorithm in C++. This implementation assumes that the graph is represented using an adjacency list and uses the Union-Find data structure to efficiently detect cycles.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};
// Structure to represent a disjoint set
struct DisjointSet {
    int *parent, *rank;
    int n;
    DisjointSet(int n) {
        this->n = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    // Find the set to which an element belongs
    int find(int u) {
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
    // Union of two sets
    void unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rank[rootU] < rank[rootV])
            parent[rootU] = rootV;
        else if (rank[rootU] > rank[rootV])
            parent[rootV] = rootU;
        else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
};
// Comparator function to sort edges by weight
bool compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}
// Kruskal's Algorithm to find Minimum Spanning Tree
void kruskal(vector<Edge>& edges, int n) {
    // Sort edges by weight
    sort(edges.begin(), edges.end(), compareEdges);
    // Initialize disjoint set
    DisjointSet ds(n);
    cout << "Minimum Spanning Tree:" << endl;
    int totalWeight = 0;
    // Process each edge
    for (Edge edge : edges) {
        int rootSrc = ds.find(edge.src);
        int rootDest = ds.find(edge.dest);
        // If adding the edge doesn't create a cycle, include it in the MST
        if (rootSrc != rootDest) {
            cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
            totalWeight += edge.weight;
            ds.unionSets(rootSrc, rootDest);
        }
    }
    cout << "Total Weight of MST: " << totalWeight << endl;
}
int main() {
    // Example graph represented by an adjacency list
    int n = 4; // Number of vertices
    vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };
    kruskal(edges, n);

Output:

Minimum Spanning Tree:

2 – 3 : 4

0 – 3 : 5

0 – 1 : 10

Total Weight of MST: 19

Seeking knowledge about various types of polymorphism? Explore our detailed blog explaining the types of polymorphism in C++

Applications of Kruskal’s Algorithm in DAA

Kruskal’s Algorithm finds applications in various domains within the field of Design and Analysis of Algorithms (DAA). Its ability to efficiently determine the minimum spanning tree of a graph makes it valuable in solving optimization problems related to connectivity. Here are some applications:

  • Network Design
    In computer networks, Kruskal’s Algorithm is applied to optimize the layout of connections between routers or servers. By constructing the minimum spanning tree, the algorithm helps minimize the cost or latency of network communication.
  • Circuit Design
    Electrical circuits often involve connecting various components efficiently to minimize the total wire length. Kruskal’s Algorithm is employed to design circuits with the least amount of wiring, reducing the overall cost and improving the efficiency of the circuit.
  • Transportation Networks
    Kruskal’s Algorithm is used in the design of transportation networks, such as road or railway systems. By constructing the minimum spanning tree, planners can minimize the cost of constructing new routes or connections, optimizing the overall transportation infrastructure.
  • Resource Management
    In scenarios where resources need to be distributed efficiently, such as power distribution in a power grid, Kruskal’s Algorithm aids in minimizing the total resource usage. It helps design networks that achieve the desired connectivity with the least resource consumption.
  • Cluster Analysis
    In data science and machine learning, Kruskal’s Algorithm can be applied to cluster analysis. It helps identify the most significant relationships or connections between data points, helping in the creation of meaningful clusters or groups.
  • Image Segmentation
    Kruskal’s Algorithm can be applied in image processing for segmentation tasks. By treating pixels as vertices and their connectivity as edges, the algorithm assists in identifying connected regions in an image, contributing to image segmentation.

Conclusion

Kruskal’s Algorithm is a powerful tool in algorithms, solving complex connectivity problems with elegance. Its efficiency is evident in optimizing networks, circuits, and resource management. As we explore algorithmic optimization, Kruskal’s stands out for its strategic and systematic design. Its significance lies in constructing minimum spanning trees, ensuring optimal solutions. Future developments may enhance scalability and adaptability, making it even more versatile in solving evolving problems.

Still have queries? You can post your doubts on our Community page.

FAQs

What is Kruskal's Algorithm used for?

Kruskal’s Algorithm is primarily used for finding the Minimum Spanning Tree (MST) in a connected, undirected graph. It minimizes the total weight of edges while ensuring all vertices are connected without forming cycles.

How does Kruskal's Algorithm handle edge weights?

Kruskal’s Algorithm initially sorts the edges in a non-decreasing order of weights. It then processes these edges in ascending order, adding the smallest available edge at each step to construct the minimum spanning tree.

What is the significance of the "disjoint set" data structure in Kruskal's Algorithm?

The disjoint-set data structure is crucial for detecting and avoiding cycles. It efficiently determines whether adding an edge will create a cycle in the spanning tree, helping maintain the acyclic property.

Does Kruskal's Algorithm always produce a unique MST for a given graph?

No, a graph may have multiple minimum spanning trees with the same total weight. Kruskal’s Algorithm, however, guarantees an MST and any of these MSTs will have the minimum possible total weight.

Can Kruskal's Algorithm handle graphs with weighted and unweighted edges simultaneously?

Yes, Kruskal’s Algorithm can handle graphs with both weighted and unweighted edges. For unweighted edges, all weights are considered equal, and the algorithm still constructs the minimum spanning tree accordingly.

Are there scenarios where Kruskal's Algorithm might not be the most efficient choice?

Kruskal’s Algorithm may not be the most efficient in dense graphs with a large number of edges. In such cases, algorithms like Prim’s Algorithm, which has better time complexities for dense graphs, might be more suitable.

Can Kruskal's Algorithm handle graphs with negative edge weights?

No, Kruskal’s Algorithm is not designed to handle graphs with negative edge weights. For such scenarios, algorithms like Bellman-Ford or Dijkstra’s Algorithm are more appropriate.

Course Schedule

Name Date Details
Python Course 22 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 29 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 06 Jul 2024(Sat-Sun) Weekend Batch
View Details

About the Author

Senior Consultant Analytics & Data Science

Presenting Sahil Mattoo, a Senior Consultant Analytics & Data Science at Eli Lilly and Company is an accomplished professional with 14 years of experience across data science, analytics, and technical leadership domains, demonstrates a remarkable ability to drive business insights. Sahil holds a Post Graduate Program in Business Analytics and Business Intelligence from Great Lakes Institute of Management.