Prims Algorithm C++: Story

🏔️ PRIM’S REACH — The Rise of the Radiant Thread

"A kingdom isn't made all at once. It grows thread by thread —

from one light, to many, across the darkest corners of the world."

— From the Journal of Aelius Prim, Keeper of the Crystal Thread

🌑 Prologue: The City of Isolated Flames

In the ancient land of Verdalis, the world was fragmented, not by borders, but by fear.

Each city had a flame — a glowing tower of civilization — but no roads, no paths, nothing between them.

They shivered in silence.

Then came Aelius Prim, a mapmaker, a builder, and a dreamer.

He didn’t seek to unite all lands at once. No.

He began with one spark.

And from that spark, he sought to spread light — one gentle step at a time, always choosing the closest darkness to illuminate next.

📜 The Blueprint of the Expansion

#include <iostream>

#include <vector>

#include <queue>

#include <utility>

using namespace std;

Prim gathered tools:

• A map to mark every road between cities


• A torch to light the starting city


• A lens of greed, to always find the nearest darkness worth bringing into the light

🧱 The Architect’s Scroll

class PrimMST {

    int V;

    vector<vector<pair<int, int>>> adj;



public:

    PrimMST(int V) : V(V) {

        adj.resize(V);

    }



    void addEdge(int u, int v, int w) {

        adj[u].push_back({v, w});

        adj[v].push_back({u, w});

    }

Prim was no conqueror.

He didn’t burn cities into submission — he invited them.

With addEdge(u, v, w), he recorded every possible passage:

from city u to city v, with effort w.

These were roads not yet built, only possibilities, waiting to be chosen.

The adjacency list adj held whispers of connection in both directions,

for roads, unlike war, go both ways.

🔥 The Lighting Ceremony Begins

    int buildMST(int start = 0) {

        vector<bool> visited(V, false);

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;



        pq.push({0, start});

        int totalWeight = 0;

Prim stood atop the tower of the first city.

He lifted the Crystal Thread — a radiant filament of energy — and dropped it down into the earth.

The light spread to the first node: start.

And from there, the rule was simple:

At every moment, connect the nearest city that is still in darkness.

A priority queue — a sacred compass of greed — guided his hand:

• It always chose the minimum weight edge available


• But only if it led to an unlit city
  

The visited array marked which cities had already felt the warmth.

totalWeight — a humble counter — grew with each light extended.

🕯️ The Path of Growing Light

        while (!pq.empty()) {

            auto [weight, u] = pq.top(); pq.pop();



            if (visited[u]) continue;

            visited[u] = true;

            totalWeight += weight;

Every time Prim pulled from the priority queue, he received an offer:

“Here is a road of weight, leading to city u.”

If city u was already visited, he ignored it — for he never lit what was already bright.

Otherwise:

• He accepted the road
  


• Stepped forward


• Paid the weight


• And brought another flame into the fold

One by one, the light grew.

✨ Offering Paths to Darkness

            for (auto& [v, w] : adj[u]) {

                if (!visited[v]) {

                    pq.push({w, v});

                }

            }

        }



        return totalWeight;

    }

};

Once a city was lit, Prim gazed outward from its tower:

“Which neighbors remain in the dark?

Who can I invite next, and at what cost?”

He gathered all such edges {w, v} and gently pushed them into the priority queue.

Each edge became a silent promise:

• If you are the cheapest path to darkness,
  then you will be the next torch.

No cycles. No chaos.

Just pure expansion, guided by the greedy but selfless light.

🌅 A Glowing Kingdom is Born

int main() {

    PrimMST prim(6);

    prim.addEdge(0, 1, 4);

    prim.addEdge(0, 2, 4);

    prim.addEdge(1, 2, 2);

    prim.addEdge(1, 3, 5);

    prim.addEdge(2, 3, 5);

    prim.addEdge(3, 4, 3);

    prim.addEdge(4, 5, 1);

    prim.addEdge(3, 5, 6);



    cout << "Total Cost to Illuminate the Kingdom: " << prim.buildMST() << "\n";

}

In a forgotten valley of 6 isolated cities,

Prim ignited the first crystal at node 0.

He whispered to the winds:

“Let there be connection.”

One by one, the cities lit up:

• First, city 2 — so close, so eager


• Then city 1 — bonded by old kinship


• And onward… until all were glowing

When the last road was laid, the flames formed a lattice across the land.

A web not of domination, but shared brilliance.

And the scroll declared:

"Total Cost to Illuminate the Kingdom: 15"

🧠 The Wisdom Etched in Fire

• 
  adj[u] — whispers of every city’s neighbors and their cost


• 
  priority_queue — the greedy seer, always guiding toward the closest unknown


• 
  visited[] — the map of light, marking who has been saved


• 
  buildMST() — the silent ritual, lighting one flame at a time until the kingdom glows

"Do not rush to connect everything at once.

Begin where you stand.

And always reach for the nearest shadow waiting for light."

Thus was the story of Aelius Prim.

He didn't conquer with armies.

He built with care.

And the kingdom he left behind was not a throne of gold...

But a web of roads that gleamed like constellations from the stars.