DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Kruskal Algorithm C++: Story

#algorithms #cpp #programming

🏰 KRUSKAL: The Last Roadmaker — A Tale of Steel and Shadows

“A kingdom is not built by kings alone, but by the silent architects who connect every soul.”
— From the Scroll of Edges, hidden deep beneath the Spine of the World

🕯️ Prologue: A Shattered Continent

Long ago, the world was not one kingdom but a scattering of hundreds.

Every village, every mountain fortress, every lakeside manor — stood alone, afraid, proud, disconnected.

The gods of chaos danced in the space between them. No road dared bridge two lands, for the forests were cursed and the rivers whispered death.

Yet hope stirred. Because roads… roads connect hearts.

And thus entered the man who would not seek a throne — but a network.

His name was Kruskal, the Last Roadmaker.

🛠️ The Scroll of Stone and Connection 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
Enter fullscreen mode Exit fullscreen mode

Before the first stone was laid, Kruskal carved his blueprints into scrolls of steel.

He would need:

  • Eyes to see all edges
  • Memory to remember where paths have formed
  • A spell to prevent cycles — to keep his roads from looping endlessly through cursed lands

🌉 The Blueprint of the World 

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};
Enter fullscreen mode Exit fullscreen mode

Every time a villager came to Kruskal, they whispered of a possible road:

“Between village u and v, with weight of effort = w.”

Kruskal recorded it in an Edge — a sacred bond, but not yet chosen.

He kept a vault of all such roads, and before building anything,
he vowed to choose only the lightest roads — the least cost —
for every stone must be earned.

Hence, he sorted his edges by weight.

🧩 The Spell of Unity: Union-Find Runes 

class UnionFind {
    vector<int> 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 v) {
        if (parent[v] == v) return v;
        return parent[v] = find(parent[v]);
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;

        if (rank[a] < rank[b])
            parent[a] = b;
        else if (rank[a] > rank[b])
            parent[b] = a;
        else {
            parent[b] = a;
            rank[a]++;
        }

        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Kruskal was no fool.

He knew that roads could lead to cycles, and cycles lead to madness —
looped trade routes that waste time and invite bandits.

So he turned to the Monks of the Rooted Tree, who gifted him the Union-Find spell.

Through find(), he would know who was already connected.
Through unite(), he would bind two lands together if — and only if — they weren’t already one.

“Never connect what's already joined,” they warned.
“Lest your road be cursed.”

🛡️ The Roadmaker’s Journey: Kruskal’s Algorithm 

class KruskalMST {
    int V;
    vector<Edge> edges;

public:
    KruskalMST(int V) : V(V) {}

    void addEdge(int u, int v, int w) {
        edges.push_back({u, v, w});
    }

    int buildMST() {
        sort(edges.begin(), edges.end());
        UnionFind uf(V);
        int mstWeight = 0;

        for (auto& edge : edges) {
            if (uf.unite(edge.u, edge.v)) {
                mstWeight += edge.weight;
                // Optionally record the edge for printing the MST
            }
        }

        return mstWeight;
    }
};
Enter fullscreen mode Exit fullscreen mode

And now, Kruskal began his mission.

With V villages, he gathered every possible road.
From his archives of edges, he sorted them — lightest to heaviest — for he had no time for foolish burdens.

With each edge, he cast his Union spell:

  • If the lands were unconnected → he built the road, adding its cost to mstWeight
  • If already connected → he ignored it, no matter how tempting

No favor. No politics. Just logic and connection without cycles.

🏁 The Age of Unity: Final Call 

int main() {
    KruskalMST realm(6);
    realm.addEdge(0, 1, 4);
    realm.addEdge(0, 2, 4);
    realm.addEdge(1, 2, 2);
    realm.addEdge(1, 3, 5);
    realm.addEdge(2, 3, 5);
    realm.addEdge(3, 4, 3);
    realm.addEdge(4, 5, 1);
    realm.addEdge(3, 5, 6);

    cout << "Minimum Total Weight of Roads: " << realm.buildMST() << "\n";
}
Enter fullscreen mode Exit fullscreen mode

In a trial of 6 broken kingdoms, Kruskal rose once again.

With each addEdge(), a villager whispered of possibility.

With buildMST(), the Last Roadmaker chose not what was possible, but what was necessary —
uniting every kingdom with the minimum cost, leaving no cycles behind, only harmony.

And when the roads were complete, the scribes carved the number deep in mountain stone:

"Minimum Total Weight of Roads: 15"

Peace through connection. Strength through minimalism.

💫 Epilogue: The Magic You Must Never Forget

  • Edge — a story of two lands, and the weight to connect them
  • UnionFind — the ancient tree of kingship and the secret to prevent cursed cycles

  • KruskalMST — the Roadmaker's master plan

    • Sort all possible roads
    • One by one, connect only the unconnected
    • Always choose the lightest path forward

  • No cycles. No greed. No waste.

“The king is remembered by his crown.
But the roadmaker is remembered by every step ever walked.”

And so, in every land that once stood divided,
the people remembered not who ruled them…
but the one who connected them.

His name, whispered on every bridge, every trail, every cobbled street:

Kruskal.

Top comments (0)