Kruskal's Data Structure and Algorithm

Algorithm

It seems like you're referring to Kruskal's algorithm, which is a popular algorithm in computer science, specifically used for finding the minimum spanning tree of a connected, undirected graph. A minimum spanning tree is a subset of the edges of a graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

Kruskal's algorithm works by sorting all the edges in the graph in non-decreasing order of their weights and then adding them to the spanning tree one by one, while ensuring that no cycles are formed. Here's a high-level overview of the algorithm:

Sort Edges: Sort all the edges in the graph in non-decreasing order of their weights.
Initialize: Create an empty graph to represent the minimum spanning tree.
Iterate through Edges: Iterate through the sorted edges, and for each edge, check if adding it to the current minimum spanning tree would create a cycle. If not, add the edge to the spanning tree.
Stop: Continue this process until the spanning tree has $V - 1$ edges, where $V$ is the number of vertices in the original graph.

Kruskal's algorithm is greedy and has a time complexity of $O (E lo g E)$ , where $E$ is the number of edges in the graph. It's worth noting that Kruskal's algorithm can be efficient for sparse graphs where $E$ is much less than $V^{2}$ .

Code Examples

#1 Kruskal's implement in Python

Code - Python Programming

class UnionFind:
    def __init__(self, vertices):
        self.parent = {vertex: vertex for vertex in vertices}
        self.rank = {vertex: 0 for vertex in vertices}

    def find(self, vertex):
        if self.parent[vertex] != vertex:
            self.parent[vertex] = self.find(self.parent[vertex])
        return self.parent[vertex]

    def union(self, vertex1, vertex2):
        root1 = self.find(vertex1)
        root2 = self.find(vertex2)

        if root1 != root2:
            if self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            elif self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            else:
                self.parent[root1] = root2
                self.rank[root2] += 1


def kruskal(graph):
    edges = []
    for vertex in graph:
        for neighbor, weight in graph[vertex]:
            edges.append((weight, vertex, neighbor))

    edges.sort()  # Sort edges by weight in ascending order

    minimum_spanning_tree = []
    union_find = UnionFind(graph.keys())

    for edge in edges:
        weight, vertex1, vertex2 = edge
        if union_find.find(vertex1) != union_find.find(vertex2):
            minimum_spanning_tree.append((vertex1, vertex2, weight))
            union_find.union(vertex1, vertex2)

    return minimum_spanning_tree


# Example usage:
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

result = kruskal(graph)
print("Minimum Spanning Tree:", result)

Copy The Code & Try With Live Editor

#2 Kruskal's implement in Java

Code - Java Programming

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Edge {
    int source, destination, weight;

    public Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

class Graph {
    int vertices;
    List < Edge> edges;

    public Graph(int vertices) {
        this.vertices = vertices;
        this.edges = new ArrayList < >();
    }

    public void addEdge(int source, int destination, int weight) {
        Edge edge = new Edge(source, destination, weight);
        edges.add(edge);
    }

    public void kruskalMST() {
        // Sort edges by weight in ascending order
        Collections.sort(edges, Comparator.comparingInt(e -> e.weight));

        int[] parent = new int[vertices];
        for (int i = 0; i  <  vertices; i++) {
            parent[i] = i;
        }

        List < Edge> result = new ArrayList<>();

        for (Edge edge : edges) {
            int root1 = find(parent, edge.source);
            int root2 = find(parent, edge.destination);

            if (root1 != root2) {
                result.add(edge);
                union(parent, root1, root2);
            }
        }

        // Print the MST edges
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : result) {
            System.out.println(edge.source + " - " + edge.destination + " : " + edge.weight);
        }
    }

    private int find(int[] parent, int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent, parent[vertex]);
        }
        return parent[vertex];
    }

    private void union(int[] parent, int root1, int root2) {
        parent[root1] = root2;
    }
}

public class KruskalsAlgorithm {
    public static void main(String[] args) {
        int vertices = 4;
        Graph graph = new Graph(vertices);

        // Add edges to the graph
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);

        // Find and print the Minimum Spanning Tree
        graph.kruskalMST();
    }
}

Copy The Code & Try With Live Editor

#3 Kruskal's implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};

// Structure to represent a subset for union-find
struct Subset {
    int parent;
    int rank;
};

// Function to find the set of an element in a disjoint set
int find(struct Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

// Function to perform union of two subsets
void unionSets(struct Subset subsets[], int x, int y) {
    int rootX = find(subsets, x);
    int rootY = find(subsets, y);

    if (subsets[rootX].rank  <  subsets[rootY].rank)
        subsets[rootX].parent = rootY;
    else if (subsets[rootX].rank > subsets[rootY].rank)
        subsets[rootY].parent = rootX;
    else {
        subsets[rootX].parent = rootY;
        subsets[rootY].rank++;
    }
}

// Function to compare two edges based on their weights
int compareEdges(const void* a, const void* b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Function to run Kruskal's algorithm
void kruskalMST(struct Edge edges[], int V, int E) {
    // Allocate memory for subsets
    struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));

    // Initialize subsets
    for (int i = 0; i  <  V; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }

    // Sort the edges in non-decreasing order by weight
    qsort(edges, E, sizeof(edges[0]), compareEdges);

    printf("Minimum Spanning Tree using Kruskal's algorithm:\n");

    int mstWeight = 0; // Total weight of the MST

    for (int i = 0, j = 0; j  <  V - 1 && i < E; i++) {
        // Pick the smallest edge
        struct Edge nextEdge = edges[i];

        // Find the sets of the source and destination vertices
        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);

        // If including this edge does not cause a cycle, add it to the MST
        if (x != y) {
            printf("(%d, %d) -> %d\n", nextEdge.src, nextEdge.dest, nextEdge.weight);
            mstWeight += nextEdge.weight;
            unionSets(subsets, x, y);
            j++;
        }
    }

    printf("Total Weight of MST: %d\n", mstWeight);

    // Free allocated memory
    free(subsets);
}

int main() {
    // Example graph representation
    int V = 4; // Number of vertices
    int E = 5; // Number of edges
    struct Edge edges[] = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    // Run Kruskal's algorithm
    kruskalMST(edges, V, E);

    return 0;
}

Copy The Code & Try With Live Editor

#4 Kruskal's implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge
struct Edge {
    int source, destination, weight;

    // Comparator function for sorting edges based on weight
    bool operator < (const Edge& other) const {
        return weight < other.weight;
    }
};

class Kruskal {
private:
    int vertices;
    vector < Edge> edges;

public:
    Kruskal(int v) : vertices(v) {}

    // Add an edge to the graph
    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }

    // Find set of an element i
    int findSet(vector<int>& parent, int i) {
        if (parent[i] == -1)
            return i;
        return findSet(parent, parent[i]);
    }

    // Union of two sets
    void unionSets(vector<int>& parent, int x, int y) {
        int xroot = findSet(parent, x);
        int yroot = findSet(parent, y);
        parent[xroot] = yroot;
    }

    // Function to run Kruskal's algorithm
    void kruskalMST() {
        // Sort edges in non-decreasing order of weight
        sort(edges.begin(), edges.end());

        vector<int> parent(vertices, -1);

        for (const Edge& edge : edges) {
            int x = findSet(parent, edge.source);
            int y = findSet(parent, edge.destination);

            // If including this edge doesn't cause a cycle, include it in the MST
            if (x != y) {
                cout << edge.source << " - " << edge.destination << " : " << edge.weight << endl;
                unionSets(parent, x, y);
            }
        }
    }
};

int main() {
    Kruskal g(4);

    // Example graph
    g.addEdge(0, 1, 10);
    g.addEdge(0, 2, 6);
    g.addEdge(0, 3, 5);
    g.addEdge(1, 3, 15);
    g.addEdge(2, 3, 4);

    cout << "Edges in the Minimum Spanning Tree:\n";
    g.kruskalMST();

    return 0;
}

Copy The Code & Try With Live Editor

Demonstration

Kruskal's Data Structure and Algorithm

Try With Live Editor

Category - Data Structure and Algorithm Maniruzzaman Akash 1 year ago 294 0