Kruskal’s MST in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int p[100];
int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }
int main() {
    int e = 5, edges[5][3] = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}}, i, a, b;
    for (i = 0; i < 100; i++) p[i] = i;
    for (i = 0; i < e-1; i++) // simple bubble sort for small size
        for (int j = i+1; j < e; j++)
            if (edges[i][2] > edges[j][2]) {
                int t[3]; for (int k = 0; k < 3; k++) t[k] = edges[i][k], edges[i][k] = edges[j][k], edges[j][k] = t[k];
            }
    for (i = 0; i < e; i++) {
        a = find(edges[i][0]); b = find(edges[i][1]);
        if (a != b) {
            printf("%d-%d (%d)\n", edges[i][0], edges[i][1], edges[i][2]);
            p[a] = b;
        }
    }
}

C Output

Input:
Edges: {0-1,10}, {0-2,6}, {0-3,5}, {1-3,15}, {2-3,4}
Output:
Input: 5 edges

Output:
2-3 (4)
0-3 (5)
0-1 (10)

C++ Program

#include <bits/stdc++.h>
using namespace std;
int find(vector<int>& p, int x) {
    return p[x] == x ? x : p[x] = find(p, p[x]);
}
int main() {
    vector<tuple<int,int,int>> e = {{1,2,3},{1,3,1},{2,3,1},{0,1,2}};
    sort(e.begin(), e.end(), [](auto a, auto b){ return get<2>(a) < get<2>(b); });
    vector<int> p(4); iota(p.begin(), p.end(), 0);
    for (auto [u,v,w] : e)
        if (find(p,u) != find(p,v)) {
            cout << u << "-" << v << " (" << w << ")\n";
            p[find(p,u)] = find(p,v);
        }
}

C++ Output

Input:
Edges: {1-3,1}, {2-3,1}, {0-1,2}, {1-2,3}
Output:
Input: 4 edges

Output:
1-3 (1)
2-3 (1)
0-1 (2)

JAVA Program

import java.util.*;
class Main {
    static int find(int[] p, int x) {
        return p[x] == x ? x : (p[x] = find(p, p[x]));
    }
    public static void main(String[] args) {
        int[][] e = {{0,1,1},{1,2,2},{0,2,3}};
        Arrays.sort(e, Comparator.comparingInt(a -> a[2]));
        int[] p = new int[3]; for (int i = 0; i < 3; i++) p[i] = i;
        for (int[] ed : e) {
            int a = find(p, ed[0]), b = find(p, ed[1]);
            if (a != b) {
                System.out.println(ed[0] + "-" + ed[1] + " (" + ed[2] + ")");
                p[a] = b;
            }
        }
    }
}

JAVA Output

Input:
Edges: {0-1,1}, {1-2,2}, {0-2,3}
Output:
Input: 3 edges

Output:
0-1 (1)
1-2 (2)

Python Program

edges = [(0, 1, 5), (1, 2, 3), (0, 2, 6)]
p = list(range(3))
def find(x): return x if p[x] == x else find(p[x])
edges.sort(key=lambda x: x[2])
for u, v, w in edges:
    a, b = find(u), find(v)
    if a != b:
        print(f"{u}-{v} ({w})")
        p[a] = b

Python Output

Input:
Edges: {0-1,5}, {1-2,3}, {0-2,6}
Output:
Input: 3 edges
Output:
1-2 (3)
0-1 (5)

In-Depth Explanation

Example

In the following Python example:

Edges: 0-1(5), 1-2(3), 0-2(6)

Kruskal's Algorithm begins with sorting all edges by weight:

1-2 (3) → added

0-1 (5) → added

0-2 (6) → skipped (would create a cycle)

The cost of MST = 3 + 5 = 8

Real-Life Analogy

Picture linking cities with highways where you prefer the lowest overall cost and no cycles. Kruskal's Algorithm allows you to choose the lowest-cost highways one at a time only if they won't form a cycle, analogous to city planners attempting to minimize infrastructure cost while maintaining complete connectivity.

Why It Matters

Kruskal's Algorithm is one of the two most popular MST algorithms (the other being Prim's).

It's:

Easy and greedy

Works best on sparse graphs

Excellent when edges are provided and not adjacency lists

Especially useful in:

Network design (cables, water, electricity)

Clustering in machine learning

Image segmentation in computer vision

Learning Insights

Through Kruskal's Algorithm, you learn:

Disjoint Set Union (DSU) for cycle detection

Why greedy approaches can still produce optimal solutions

Sorting and union-find concepts in graphs

You also solidify your grasp of edge-based traversal, compare it with Prim's node-based and understand how greedy techniques hold true for trees.

Interview & Real-World Use

Kruskal's Algorithm is prevalent in:

Graph and MST problems

Design problems such as road, rail, network cost reduction

Problems incorporating DSU or cycle detection

It's real-world applicable in:

Network/utility plan design

Constructing hierarchical trees (hierarchies, clusters)

Optimizing paths in low-cost travel planners

Kruskal's Algorithm is a building block of graph theory, enabling us to quickly construct a Minimum Spanning Tree at minimum edge cost and without cycles. Its greedy nature and union-find process enable you to grasp basic principles in graph optimization and disjoint sets. Whether coding for a coding interview or planning a network topology, Kruskal's Algorithm shows you how to think about optimality, efficiency, and connectivity. The above examples in C, C++, Java, and Python provide you with a balanced view to excel at both academic issues and practical uses.