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:

• Introduction to Kruskal’s Algorithm in DAA
  • Spanning Tree
  • Minimum Spanning Tree
• How Does Kruskal’s Algorithm Work 
  • Example
• Practical Implementation of Kruskal’s Algorithm 
• Applications of Kruskal’s Algorithm in DAA
• Conclusion

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. 

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.

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:

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:

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