Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 25

    Kruskal and Union Find Code

    Updated: Algorithms No Comments5 Mins Readdevangini123By

    Example:

      Sorted Edges:

    • 1 → 0, 1
    • 2 → 3, 2
    • 3 → 4, 3
    • 2 → 5, 6
    • 2 → 4, 7
    • 0 → 2, 8
    • 1 → 2, 9
    • 4 → 5, 10

    Exploring Edges

    • 1 → 0, 1
    • 2 → 3, 2
    • 3 → 4, 3
    • 2 → 5, 6
    • 2 → 4, 7
      • Cycle Detected (Skip)
    • 0 → 2, 8
    • 1 → 2, 9
      • Cycle Detected (Skip)
    • 4 → 5, 10
      • Cycle Detected (Skip)

      MST => 1 + 2 + 3 + 6 + 8 => 20

    Code

    class UnionFind {
    constructor(n) {
        this.parent = new Array(n).fill(0).map((_, i) => i);
        this.rank = new Array(n).fill(0);
    }

    // finds the root of node x
    find(x) {
        if(this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y){
        let rootX = this.find(x);
        let rootY = this.find(y);
        // cycle Detected
        if(rootX === rootY) return false;
        
        // union based on rank
        if(this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        }
        else if(this.rank[rootY] > this.rank[rootX]) {
            this.parent[rootX] = rootY;
        }
        else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

// Kruskal Algorithm
function Kruskal(n, edges) {
    // sort the edges based on weights
    edges.sort((a, b) => a[2] - b[2]);

    let uf = new UnionFind(n);
    let mstCost = 0;

    for(let [x, y, w] of edges) {
        if (uf.union(x, y)) {
            mstCost = mstCost + w;
        } 
    }
    return mstCost;
}

const edges = [
    [0, 1, 4], [0, 2, 4], [1, 2, 2],
    [2, 3, 3], [2, 5, 2], [2, 4, 4],
    [3, 4, 3], [5, 4, 3]
];

console.log(Kruskal(6, edges));

      class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX == rootY:
            return False

        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootY] > self.rank[rootX]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True


def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    mst_cost = 0

    for x, y, w in edges:
        if uf.union(x, y):
            mst_cost += w

    return mst_cost


edges = [
    [0, 1, 4], [0, 2, 4], [1, 2, 2],
    [2, 3, 3], [2, 5, 2], [2, 4, 4],
    [3, 4, 3], [5, 4, 3]
]

print(kruskal(6, edges))

    
    import java.util.*;

class UnionFind {
    int[] parent, rank;

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

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else if (rank[rootY] > rank[rootX])
            parent[rootX] = rootY;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

public class KruskalMST {

    public static int kruskal(int n, int[][] edges) {
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
        UnionFind uf = new UnionFind(n);
        int mstCost = 0;

        for (int[] e : edges) {
            if (uf.union(e[0], e[1]))
                mstCost += e[2];
        }
        return mstCost;
    }

    public static void main(String[] args) {
        int[][] edges = {
            {0,1,4},{0,2,4},{1,2,2},
            {2,3,3},{2,5,2},{2,4,4},
            {3,4,3},{5,4,3}
        };

        System.out.println(kruskal(6, edges));
    }
}
    
    #include <bits/stdc++.h>
using namespace std;

class UnionFind {
    vector parent, rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else if (rank[rootY] > rank[rootX])
            parent[rootX] = rootY;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
};

int kruskal(int n, vector>& edges) {
    sort(edges.begin(), edges.end(),
         [](auto &a, auto &b) { return a[2] < b[2]; });

    UnionFind uf(n);
    int mstCost = 0;

    for (auto &e : edges) {
        if (uf.unite(e[0], e[1]))
            mstCost += e[2];
    }
    return mstCost;
}

int main() {
    vector> edges = {
        {0,1,4},{0,2,4},{1,2,2},
        {2,3,3},{2,5,2},{2,4,4},
        {3,4,3},{5,4,3}
    };

    cout << kruskal(6, edges);
}
  
    #include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x, y, w;
} Edge;

int parent[100], rankArr[100];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

int unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) return 0;

    if (rankArr[rootX] > rankArr[rootY])
        parent[rootY] = rootX;
    else if (rankArr[rootY] > rankArr[rootX])
        parent[rootX] = rootY;
    else {
        parent[rootY] = rootX;
        rankArr[rootX]++;
    }
    return 1;
}

int cmp(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int kruskal(int n, Edge edges[], int m) {
    qsort(edges, m, sizeof(Edge), cmp);

    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rankArr[i] = 0;
    }

    int mstCost = 0;

    for (int i = 0; i < m; i++) {
        if (unionSet(edges[i].x, edges[i].y))
            mstCost += edges[i].w;
    }
    return mstCost;
}

int main() {
    Edge edges[] = {
        {0,1,4},{0,2,4},{1,2,2},
        {2,3,3},{2,5,2},{2,4,4},
        {3,4,3},{5,4,3}
    };

    printf("%d\n", kruskal(6, edges, 8));
    return 0;
}

    using System;
using System.Collections.Generic;

class UnionFind {
    int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public int Find(int x) {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    public bool Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else if (rank[rootY] > rank[rootX])
            parent[rootX] = rootY;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

class Program {
    static int Kruskal(int n, List edges) {
        edges.Sort((a, b) => a[2] - b[2]);
        UnionFind uf = new UnionFind(n);
        int mstCost = 0;

        foreach (var e in edges) {
            if (uf.Union(e[0], e[1]))
                mstCost += e[2];
        }
        return mstCost;
    }

    static void Main() {
        var edges = new List {
            new[] {0,1,4}, new[] {0,2,4}, new[] {1,2,2},
            new[] {2,3,3}, new[] {2,5,2}, new[] {2,4,4},
            new[] {3,4,3}, new[] {5,4,3}
        };

        Console.WriteLine(Kruskal(6, edges));
    }
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us