Minimum spanning tree — Kruskal আর Prim, প্রমাণসহ

১ · সমস্যা — সব উপজেলা জুড়তে সবচেয়ে কম খরচ

একটি জেলার ছয়টি উপজেলাকে ফাইবার অপটিক কেবল দিয়ে জুড়তে হবে, যাতে যেকোনো উপজেলা থেকে যেকোনো উপজেলায় ইন্টারনেটের ডেটা যেতে পারে — সরাসরি না হলেও অন্য উপজেলা ঘুরে। প্রকৌশলীরা জরিপ করে নয়টি সম্ভাব্য কেবল-পথ বের করেছেন, প্রতিটির খরচ (কোটি টাকায়) জানা। সব পথে কেবল টানার দরকার নেই; প্রশ্ন হলো: কোন কোন পথ বেছে নিলে সব উপজেলা যুক্ত হয়, আর মোট খরচ সবচেয়ে কম হয়? পল্লী বিদ্যুতায়নের লাইন, গ্রামের পানির পাইপ বা একটি অফিসের কম্পিউটার নেটওয়ার্ক — সবখানেই একই প্রশ্ন।

পর্ব ৩৯-এর ভাষায় উপজেলাগুলো vertex, কেবল-পথগুলো edge, আর প্রতিটি edge-এর গায়ে একটি সংখ্যা — খরচ বা ওজন। এমন গ্রাফকে বলে weighted graph. কেবল দুই দিকেই ডেটা নেয়, তাই গ্রাফটি undirected. আমাদের উদাহরণ গ্রাফটি এই পর্বের সব ডায়াগ্রাম আর কোডে একই থাকবে:

কেন উত্তর সবসময় একটি tree

ধরুন আপনার বেছে নেওয়া কেবলগুলোর মধ্যে একটি cycle আছে — যেমন A–B, B–C আর C–A তিনটিই নেওয়া। তাহলে cycle-এর যেকোনো একটি কেবল তুলে ফেললেও সবাই যুক্ত থাকে, কারণ ওই দুই উপজেলার মধ্যে cycle-এর বাকি অংশ দিয়ে ঘুরে যাওয়ার পথ আছে। আর খরচ কমে (সব খরচ ধনাত্মক হলে)। তাই সবচেয়ে সস্তা সমাধানে কোনো cycle থাকতে পারে না। Cycle-হীন, connected গ্রাফই হলো tree (পর্ব ২৬): V টি vertex-এ ঠিক V − 1 টি edge.

সব spanning tree গুনে দেখার brute force কি চলে? না। Cayley-র সূত্র (Arthur Cayley, ১৮৮৯) বলে, n টি vertex-এর সম্পূর্ণ গ্রাফে (প্রতি জোড়ার মধ্যে edge) nⁿ⁻² টি আলাদা spanning tree. মাত্র ২০টি উপজেলায় সেটি 20¹⁸ ≈ 2.6 × 10²³ — সেকেন্ডে একশো কোটি tree দেখলেও প্রায় ৮০ লাখ বছর লাগবে। আমাদের দরকার একটি চতুর নিয়ম, যা প্রতিটি ধাপে নিশ্চিতভাবে একটি “ঠিক” edge বেছে নেয়। সেই নিয়ম আসে দুটি সরল সত্য থেকে — cut property আর cycle property.

২ · Cut property আর cycle property — প্রমাণসহ

একটি cut (S, V − S) হলো vertex-গুলোকে দুটি অশূন্য ভাগে ভাগ করা — উপমার নদী। যে edge-এর এক প্রান্ত S-এ আর অন্য প্রান্ত V − S-এ, সেটি cut-কে পার হয় — crossing edge. পার হওয়া edge-গুলোর মধ্যে যার ওজন সবচেয়ে কম, সেটি ওই cut-এর light edge.

প্রমাণ (exchange argument): ধরুন e = (u, v), u ∈ S, v ∈ V − S, আর একটি MST T-তে e নেই — বিরোধে পৌঁছানোর জন্য এটি ধরে নিই।

1. T একটি spanning tree, তাই T-তে u থেকে v-তে ঠিক একটি পথ P আছে।
2. P শুরু হয় S-এ (u), শেষ হয় V − S-এ (v). তাই P-এর কোথাও অন্তত একবার পাড় বদলাতে হয় — P-এর একটি edge f আছে, যেটিও cut পার হয়। f ≠ e, কারণ e T-তে নেই।
3. T − f: f সরালে tree দুই টুকরো হয়, আর u ও v পড়ে আলাদা টুকরোয় (তাদের একমাত্র পথটি f দিয়েই যেত)।
4. T′ = T − f + e: e ঠিক ওই দুই টুকরোকে আবার জোড়ে। T′-এ V − 1 টি edge, সব vertex যুক্ত — অর্থাৎ T′ একটি spanning tree.
5. w(T′) = w(T) − w(f) + w(e). e হলো cut-এর সবচেয়ে হালকা crossing edge আর ওজন সব আলাদা, তাই w(e) < w(f), ফলে w(T′) < w(T). কিন্তু T ছিল minimum — বিরোধ। ∎

ওজনে সমতা থাকলে শেষ ধাপে শুধু w(e) ≤ w(f) পাই, তাই w(T′) ≤ w(T): T′-ও একটি MST, আর তাতে e আছে। নিচের ডায়াগ্রামে আমাদের গ্রাফেই প্রমাণটি চালিয়ে দেখুন। Cut: S = ওপরের চার উপজেলা {A, B, C, D}, V − S = {E, F}.

Cycle property — উল্টো দিকের নিয়ম

প্রমাণ: ধরুন একটি MST T-তে f = (x, y) আছে। T থেকে f সরালে tree দুই টুকরো হয় — এটি একটি cut, যার এক পাশে x, অন্য পাশে y. Cycle C-এর বাকি অংশ x থেকে y-তে একটি পথ, যা f ব্যবহার করে না; সেই পথ কোথাও না কোথাও এই cut পার হয় — একটি edge g ∈ C, g ≠ f. তাহলে T − f + g একটি spanning tree, আর w(g) < w(f) (f একাই সবচেয়ে ভারী), তাই সেটি T-এর চেয়ে হালকা — বিরোধ। ∎ আমাদের গ্রাফে cycle A–B–C-তে সবচেয়ে ভারী B–C (৫), cycle C–D–E-তে C–E (৮), cycle D–E–F-তে D–F (৯) — তিনটির কোনোটিই MST-তে থাকবে না। Cut property বলে “কোন edge নিতেই হবে”, cycle property বলে “কোন edge কখনো নেওয়া যাবে না”.

সব ওজন আলাদা হলে MST একটাই

দাবি: সব edge-এর ওজন আলাদা হলে MST অনন্য। প্রমাণ: ধরুন দুটি আলাদা MST আছে, T₁ আর T₂. দুটির মধ্যে যেসব edge শুধু একটিতে আছে (symmetric difference), তাদের মধ্যে সবচেয়ে হালকাটি e; ধরি e ∈ T₁, e ∉ T₂. T₂-তে e যোগ করলে একটি cycle হয়। T₁-এ cycle নেই, তাই এই cycle-এর অন্তত একটি edge f T₁-এ নেই — f ∈ T₂ − T₁, অর্থাৎ f-ও symmetric difference-এ। e সেখানে সবচেয়ে হালকা আর ওজন আলাদা, তাই w(e) < w(f). তাহলে T₂ + e − f একটি spanning tree, T₂-এর চেয়ে হালকা — বিরোধ। ∎ উল্টোটি সত্য নয়: কিছু ওজন সমান হলেও MST অনন্য হতে পারে (যেমন গ্রাফটি নিজেই একটি tree হলে)।

৩ · Generic greedy MST — প্রতিবার একটি নিরাপদ edge

Cut property থেকে সরাসরি একটি greedy কাঠামো পাওয়া যায়। একটি edge-এর সেট A রাখুন, শুরুতে খালি। প্রতি ধাপে এমন একটি edge যোগ করুন, যা যোগ করার পরেও A কোনো না কোনো MST-এর অংশ থাকে — এমন edge-কে বলে A-এর জন্য safe edge. V − 1 বার এটি করলে A নিজেই একটি MST. এই কাঠামোকে বলা হয় generic MST অ্যালগরিদম (CLRS-এর নাম)।

Pseudocode — generic MST (any vertex numbering)

GenericMST(G, w):
    A = { }                               // invariant: A is a subset of some MST
    while A has fewer than |V| - 1 edges:
        choose a cut (S, V - S) that no edge of A crosses
        e = a light edge crossing that cut  // safe by the cut property
        A = A + { e }
    return A

কেন safe: Loop invariant — “A কোনো একটি MST T-এর উপসেট”. শুরুতে খালি সেট, সত্য। এখন একটি cut নিন, যা A-এর কোনো edge পার হয় না (CLRS-এর ভাষায় cut A-কে respect করে), আর তার light edge e. e ∈ T হলে কিছু করার নেই। না হলে অংশ ২-এর exchange: T-এর u–v পথে একটি crossing edge f আছে; f ∉ A, কারণ A-এর কোনো edge cut পার হয় না; T′ = T − f + e-এর ওজন ≤ w(T), তাই T′-ও MST, আর A ∪ {e} ⊆ T′. Invariant টিকে রইল। প্রতি ধাপে একটি করে edge বাড়ে, তাই V − 1 ধাপে শেষ — তখন A একটি MST-এর উপসেট আর নিজেই V − 1 টি edge-এর spanning tree, অর্থাৎ A = MST. ∎

কাঠামোটি একটি প্রশ্ন খোলা রাখে: কোন cut বেছে নেব? দুটি স্বাভাবিক উত্তরই দুটি বিখ্যাত অ্যালগরিদম:

৪ · Kruskal — সস্তা থেকে দামি, cycle এড়িয়ে

Kruskal-এর অ্যালগরিদম, যা Joseph Kruskal ১৯৫৬ সালে প্রকাশ করেন, এক বাক্যে: সব edge খরচ অনুযায়ী সাজান; সস্তা থেকে দামি ক্রমে প্রতিটি edge নিন, যদি না সেটি আগে নেওয়া edge-গুলোর সাথে cycle বানায়। একটি edge (u, v) cycle বানায় ঠিক তখন, যখন u আর v আগেই একই component-এ আছে। এই প্রশ্নের দ্রুত উত্তর দেয় পর্ব ৩৩-এর disjoint set union (DSU): find(u) == find(v) হলে বাদ, না হলে নিন আর union(u, v).

Pseudocode — Kruskal (0-based vertices)

Kruskal(V, E):
    sort E by weight, cheapest first              // O(E log E)
    for each vertex v: make-set(v)
    A = { };  cost = 0
    for each edge (w, u, v) in sorted order:
        if find(u) != find(v):                    // different components: no cycle
            A = A + { (u, v) };  cost = cost + w
            union(u, v)
            if |A| == |V| - 1: break              // optional early stop
    return A, cost

কেন Kruskal ঠিক

Kruskal যখন e = (u, v) গ্রহণ করে, তখন u আর v আলাদা দলে। S = u-এর দল নিন। (১) এই cut A-কে respect করে: A-এর প্রতিটি edge কোনো একটি দলের ভেতরে, তাই কেউ S-এর সীমা পার হয় না। (২) e এই cut-এর light edge: e-এর চেয়ে সস্তা প্রতিটি edge আগেই দেখা হয়েছে — হয় গ্রহণ করা হয়েছে (তাহলে সে A-তে, cut পার হয় না), নয়তো বাদ গেছে কারণ তার দুই প্রান্ত তখন একই দলে ছিল; দল শুধু বড় হয়, তাই এখনো দুই প্রান্ত একই দলে, আর সেও cut পার হয় না। তাই e-এর চেয়ে সস্তা কোনো crossing edge নেই, আর অংশ ৩ অনুযায়ী e safe. বাদ পড়া edge-গুলো A-এর সাথে cycle বানাত, আর A যে MST-এর অংশ, সেখানে cycle থাকতে পারে না — তাই তাদের বাদ দেওয়াও নিরাপদ। ∎

জটিলতা: সর্ট O(E log E). DSU-তে V টি make-set আর 2E টি find, V − 1 টি union — union by size বা rank আর path compression-সহ মোট O(E α(V)), যা সর্টের তুলনায় নগণ্য। তাই মোট O(E log E). যেহেতু E ≤ V², log E ≤ 2 log V, তাই একই জিনিস O(E log V) লেখাও ঠিক। জায়গা: edge-এর তালিকা Θ(E) আর DSU Θ(V). খরচগুলো যদি ছোট পূর্ণসংখ্যা হয়, counting sort বা radix sort (পর্ব ২৪) দিয়ে সর্টও প্রায় রৈখিক হয়, তখন Kruskal কার্যত O(E α(V)). আরেকটি সুবিধা: গ্রাফ connected না হলেও Kruskal থামে না — প্রতিটি component-এর MST, অর্থাৎ minimum spanning forest দেয়।

৫ · Prim — একটি উপজেলা থেকে জাল ছড়ানো

Kruskal সারা জেলায় ছড়িয়ে ছিটিয়ে টুকরো বানায়, শেষে জোড়া দেয়। Prim-এর অ্যালগরিদম উল্টো স্বভাবের: একটি উপজেলা থেকে শুরু করে একটিমাত্র tree বড় করে। প্রতি ধাপে cut = (tree-র vertex, বাকি vertex), আর সেই cut-এর সবচেয়ে সস্তা edge দিয়ে নতুন একটি vertex tree-তে ঢোকে। যেমন একটি ইন্টারনেট সেবাদাতা প্রথমে জেলা সদরে অফিস খোলে, তারপর প্রতি মাসে সেই জাল থেকে সবচেয়ে সস্তায় যে উপজেলায় পৌঁছানো যায়, সেখানে কেবল টানে।

“Tree থেকে বাইরে যাওয়া সবচেয়ে সস্তা edge” বারবার খুঁজতে লাগে একটি priority queue (পর্ব ২৩). সবচেয়ে সহজ রূপটি “lazy”: নতুন vertex ঢুকলে তার সব বাইরের edge heap-এ ঢোকান; heap থেকে বের হওয়া edge-এর অন্য প্রান্ত যদি আগেই tree-তে থাকে, সেটি পুরোনো (stale) entry — ফেলে দিন। এটিই lazy deletion.

Pseudocode — Prim with a binary heap, lazy version (0-based)

Prim(G, s):
    inTree[v] = false for every v;  cost = 0
    PQ = { (0, s, s) }                            // entries (cost, vertex, from)
    while PQ is not empty:
        (w, v, from) = extract-min(PQ)
        if inTree[v]: continue                    // stale entry: skip it
        inTree[v] = true;  cost = cost + w
        if v != s: add edge (from, v) to A
        for each neighbour x of v with edge cost w2:
            if not inTree[x]: insert (w2, x, v) into PQ
    return A, cost

কেন Prim ঠিক, আর কত সময় নেয়

সঠিকতা: প্রতি ধাপে S = tree-র vertex. A-এর সব edge S-এর ভেতরে, তাই cut (S, V − S) A-কে respect করে। Heap-এ প্রতিটি crossing edge-এর অন্তত একটি entry আছে (S-এ প্রান্ত ঢোকার সময় ঢোকানো হয়েছিল), আর stale entry ফেলে দেওয়ার পর যা বের হয় তা সবচেয়ে সস্তা crossing edge — light edge. অংশ ৩ অনুযায়ী safe. ∎

Lazy heap: প্রতিটি edge দুই দিক থেকে সর্বোচ্চ একবার করে ঢোকে, তাই heap-এ মোট O(E) টি insert আর extract, প্রতিটি O(log E) = O(log V). মোট O(E log V), জায়গা O(E) (heap) + O(V + E) (adjacency list). Decrease-key-সহ indexed heap ব্যবহার করলে heap-এ প্রতি vertex একটি entry থাকে — সময় একই O(E log V), জায়গা O(V). Fibonacci heap-এ (Fredman ও Tarjan) decrease-key amortized O(1), তাই O(E + V log V) — তত্ত্বে ভালো, বাস্তবে ধ্রুবক বড়।

ঘন গ্রাফে O(V²) — heap ছাড়াই

যখন প্রায় প্রতিটি জোড়া উপজেলার মধ্যে পথ আছে (dense graph, E ≈ V²/2), তখন heap উল্টো ক্ষতি করে: O(E log V) = O(V² log V). তার বদলে একটি সরল অ্যারে key[v] রাখুন — “v-কে এখনকার tree-র সাথে জুড়তে সবচেয়ে সস্তা খরচ”. প্রতি ধাপে পুরো অ্যারে ঘুরে সবচেয়ে ছোট key-এর vertex নিন (O(V)), তারপর তার adjacency matrix-এর সারি দেখে প্রতিবেশীদের key কমান (O(V)). V টি ধাপ, মোট Θ(V²), জায়গা Θ(V²) matrix-এর জন্য — ঘন গ্রাফে এটিই সর্বোত্তম, কারণ ইনপুট পড়তেই Θ(V²) লাগে। কোনো দুই বিন্দুর দূরত্বই যেখানে খরচ (যেমন মানচিত্রের সব জোড়া উপজেলা), সেখানে এই রূপটিই চলে।

Pseudocode — dense Prim, O(V^2), cost matrix W (0-based, INF = no edge)

PrimDense(W, s):
    key[v] = INF, inTree[v] = false for every v;  key[s] = 0
    repeat |V| times:
        u = the vertex not in the tree with the smallest key   // O(V) scan
        inTree[u] = true;  cost = cost + key[u]
        for every vertex v:                                    // O(V)
            if not inTree[v] and W[u][v] < key[v]:
                key[v] = W[u][v];  parent[v] = u

৬ · কোডে Kruskal আর Prim — একই গ্রাফ, একই খরচ

এবার দুটি অ্যালগরিদম একই প্রোগ্রামে, আমাদের ছয় উপজেলার গ্রাফে। Kruskal প্রতিটি edge-এর জন্য বলে গ্রহণ (accept) না বাদ (reject); Prim বলে কোন vertex কোন edge দিয়ে যোগ হলো, আর কোন heap entry stale বলে ফেলে দেওয়া হলো। শেষ লাইনে দুটির মোট খরচ মেলানো হয় — এটি নিজের কোড যাচাইয়ের একটি সস্তা কৌশলও। DSU-তে এখানে শুধু path halving রাখা হয়েছে, কোড ছোট রাখতে; পূর্ণ DSU (union by size-সহ) পর্ব ৩৩-এ।

#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
using Edge = tuple<int, int, int>;                          // (cost, u, v)
const char* N = "ABCDEF";                                   // six upazilas, 0..5

int kruskal(int n, vector<Edge> es) {
    vector<int> p(n); iota(p.begin(), p.end(), 0);
    auto root = [&](int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; };
    sort(es.begin(), es.end());                             // cheapest first: O(E log E)
    int total = 0;
    for (auto [w, u, v] : es) {
        int ru = root(u), rv = root(v);
        if (ru == rv) { printf("  reject %c-%c %d (cycle)\n", N[u], N[v], w); continue; }
        p[ru] = rv; total += w; printf("  accept %c-%c %d\n", N[u], N[v], w);
    }
    return total;
}
int prim(int n, const vector<Edge>& es, int s = 0) {
    vector<vector<pair<int, int>>> adj(n);
    for (auto [w, u, v] : es) { adj[u].push_back({w, v}); adj[v].push_back({w, u}); }
    vector<bool> seen(n, false); int total = 0;
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;   // min-heap of (cost, vertex, from)
    pq.push({0, s, s});
    while (!pq.empty()) {
        auto [w, v, from] = pq.top(); pq.pop();
        if (seen[v]) { printf("  skip %c-%c %d (stale)\n", N[from], N[v], w); continue; }
        seen[v] = true; total += w;
        if (v != s) printf("  add %c via %c-%c %d\n", N[v], N[from], N[v], w);
        for (auto [w2, x] : adj[v]) if (!seen[x]) pq.push({w2, x, v});
    }
    return total;
}
int main() {
    vector<Edge> es = {{4,0,1}, {3,0,2}, {5,1,2}, {6,1,3}, {7,2,3}, {8,2,4}, {2,3,4}, {9,3,5}, {1,4,5}};
    puts("Kruskal:"); int k = kruskal(6, es); printf("Kruskal total = %d\n", k);
    puts("Prim from A:"); int q = prim(6, es); printf("Prim total = %d | same: %s\n", q, k == q ? "yes" : "no");
}

Kruskal:
  accept E-F 1
  accept D-E 2
  accept A-C 3
  accept A-B 4
  reject B-C 5 (cycle)
  accept B-D 6
  reject C-D 7 (cycle)
  reject C-E 8 (cycle)
  reject D-F 9 (cycle)
Kruskal total = 16
Prim from A:
  add C via A-C 3
  add B via A-B 4
  skip C-B 5 (stale)
  add D via B-D 6
  add E via D-E 2
  add F via E-F 1
  skip C-D 7 (stale)
  skip C-E 8 (stale)
  skip D-F 9 (stale)
Prim total = 16 | same: yes

import heapq
N = "ABCDEF"                                   # six upazilas, 0..5
edges = [(4, 0, 1), (3, 0, 2), (5, 1, 2), (6, 1, 3), (7, 2, 3),
         (8, 2, 4), (2, 3, 4), (9, 3, 5), (1, 4, 5)]      # (cost, u, v)

def kruskal(n, edges):
    p = list(range(n))
    def root(x):                               # DSU find with path halving
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x
    total = 0
    for w, u, v in sorted(edges):              # cheapest first: O(E log E)
        ru, rv = root(u), root(v)
        if ru == rv:
            print(f"  reject {N[u]}-{N[v]} {w} (cycle)")
        else:
            p[ru] = rv
            total += w
            print(f"  accept {N[u]}-{N[v]} {w}")
    return total

def prim(n, edges, s=0):
    adj = [[] for _ in range(n)]
    for w, u, v in edges:
        adj[u].append((w, v)); adj[v].append((w, u))
    seen, total, pq = [False] * n, 0, [(0, s, s)]   # heap of (cost, vertex, from)
    while pq:
        w, v, frm = heapq.heappop(pq)
        if seen[v]:
            print(f"  skip {N[frm]}-{N[v]} {w} (stale)"); continue
        seen[v], total = True, total + w
        if v != s: print(f"  add {N[v]} via {N[frm]}-{N[v]} {w}")
        for w2, x in adj[v]:
            if not seen[x]: heapq.heappush(pq, (w2, x, v))
    return total

print("Kruskal:"); k = kruskal(len(N), edges); print("Kruskal total =", k)
print("Prim from A:"); q = prim(len(N), edges)
print("Prim total =", q, "| same:", "yes" if k == q else "no")

Kruskal:
  accept E-F 1
  accept D-E 2
  accept A-C 3
  accept A-B 4
  reject B-C 5 (cycle)
  accept B-D 6
  reject C-D 7 (cycle)
  reject C-E 8 (cycle)
  reject D-F 9 (cycle)
Kruskal total = 16
Prim from A:
  add C via A-C 3
  add B via A-B 4
  skip C-B 5 (stale)
  add D via B-D 6
  add E via D-E 2
  add F via E-F 1
  skip C-D 7 (stale)
  skip C-E 8 (stale)
  skip D-F 9 (stale)
Prim total = 16 | same: yes

নিজে চালিয়ে দেখুন — Kruskal visualiser

নিচের টুলটি একই গ্রাফে Kruskal চালায়। শুরুতে পুরো রান কনসোলে লেখে আর শেষ অবস্থা দেখায়। শুরু থেকে চেপে তারপর পরের edge বারবার চাপুন: সবুজ মোটা দাগ = গ্রহণ, লাল ভাঙা দাগ = বাদ, কমলা সংখ্যা = এইমাত্র দেখা edge. এলোমেলো খরচ চাপলে নয়টি edge নতুন, আলাদা খরচ পায় — প্রতিবার আগে অনুমান করুন কোন edge বাদ পড়বে।

const POS = {A: [40, 30], B: [250, 30], C: [40, 135], D: [250, 135], E: [40, 240], F: [250, 240]};
const EDGES = [["A","B",4], ["A","C",3], ["B","C",5], ["B","D",6], ["C","D",7], ["C","E",8], ["D","E",2], ["D","F",9], ["E","F",1]];
let order, par, k, state, total;                   // state[i]: 0 waiting, 1 accepted, 2 rejected
const $ = id => document.getElementById(id);
function root(x) { while (par[x] !== x) { par[x] = par[par[x]]; x = par[x]; } return x; }
function reset() {
  order = EDGES.map((e, i) => i).sort((a, b) => EDGES[a][2] - EDGES[b][2]);   // cheapest first
  par = {}; for (const v in POS) par[v] = v;
  k = 0; total = 0; state = EDGES.map(() => 0);
  draw("start: edges sorted by cost");
}
function step() {
  if (k >= order.length) return draw("done: MST cost = " + total);
  const i = order[k++], [u, v, w] = EDGES[i], ru = root(u), rv = root(v);
  let msg;
  if (ru === rv) { state[i] = 2; msg = `reject ${u}-${v} ${w} (cycle)`; }
  else { par[ru] = rv; state[i] = 1; total += w; msg = `accept ${u}-${v} ${w}`; }
  console.log("  " + msg);
  draw(msg + "  |  total = " + total);
}
function draw(msg) {
  let s = "";
  EDGES.forEach(([u, v, w], i) => {
    const [x1, y1] = POS[u], [x2, y2] = POS[v], cur = k > 0 && order[k - 1] === i;
    const col = state[i] === 1 ? "#16a34a" : state[i] === 2 ? "#dc2626" : "#94a3b8";
    s += `<line x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" stroke="${col}" stroke-width="${state[i] === 1 ? 5 : 2}"${state[i] === 2 ? ' stroke-dasharray="6 4"' : ""}/>`;
    s += `<text x="${(x1 + x2) / 2 + 7}" y="${(y1 + y2) / 2 - 5}"${cur ? ' class="cur"' : ""}>${w}</text>`;
  });
  for (const v in POS) s += `<circle cx="${POS[v][0]}" cy="${POS[v][1]}" r="15"/><text x="${POS[v][0]}" y="${POS[v][1] + 5}" text-anchor="middle" class="nm">${v}</text>`;
  $("g").innerHTML = s; $("msg").textContent = msg;
}
function shuffleCosts() {
  const pool = Array.from({length: 20}, (_, i) => i + 1).sort(() => Math.random() - 0.5);
  EDGES.forEach((e, i) => { e[2] = pool[i]; });                  // distinct random costs
  console.log("new costs: " + EDGES.map(([u, v, w]) => `${u}${v}=${w}`).join(" "));
  reset();
}
$("bs").onclick = step; $("br").onclick = reset; $("bn").onclick = shuffleCosts;
console.log("Kruskal:"); reset(); while (k < order.length) step();
console.log("MST cost = " + total);

Kruskal:
  accept E-F 1
  accept D-E 2
  accept A-C 3
  accept A-B 4
  reject B-C 5 (cycle)
  accept B-D 6
  reject C-D 7 (cycle)
  reject C-E 8 (cycle)
  reject D-F 9 (cycle)
MST cost = 16

৭ · Borůvka আর MST-এর আত্মীয়রা

Borůvka-র অ্যালগরিদম রাউন্ডে রাউন্ডে চলে: প্রতি রাউন্ডে প্রতিটি component একসাথে নিজের সবচেয়ে সস্তা বাইরের edge বেছে নেয়, আর সব বাছাই করা edge একসাথে যোগ হয়। প্রতিটি বাছাই cut property-র সরাসরি প্রয়োগ (cut = ওই component বনাম বাকি সব)। প্রতিটি component অন্তত আরেকটির সাথে জোড়ে, তাই প্রতি রাউন্ডে component-এর সংখ্যা অন্তত অর্ধেক হয় — সর্বোচ্চ ⌈log₂ V⌉ রাউন্ড, প্রতিটি O(E): মোট O(E log V). সতর্কতা: ওজন সমান হলে দুই component দুটি ভিন্ন “সমান সস্তা” edge বেছে cycle বানাতে পারে — তাই সমতা ভাঙতে edge-এর index দিয়ে একটি নির্দিষ্ট নিয়ম লাগে।

রাউন্ডের ভেতরের কাজগুলো একে অন্যের ওপর নির্ভর করে না, তাই Borůvka সহজে parallel করা যায় — GPU আর বড় ডিস্ট্রিবিউটেড সিস্টেমে MST-এর জন্য এটিই প্রায়ই ভিত্তি। ১৯৯৫ সালে Karger, Klein আর Tarjan-এর randomized অ্যালগরিদম, যা expected (প্রত্যাশিত) O(E) সময়ে MST দেয়, তার ভেতরেও Borůvka-র রাউন্ড আছে।

Maximum spanning tree

কখনো উল্টোটা দরকার — যেমন প্রতিটি সংযোগের “নির্ভরযোগ্যতা” বা ব্যান্ডউইথ সবচেয়ে বেশি রেখে সব জুড়তে। Maximum spanning tree পেতে Kruskal-এ edge দামি থেকে সস্তা ক্রমে সাজান, বা সব ওজনকে −w করে সাধারণ MST চালান। দুটোই কাজ করে, কারণ cut আর cycle property-র প্রমাণ শুধু ওজনের ক্রম ব্যবহার করে। একই কারণে MST ঋণাত্মক ওজনেও ঠিক কাজ করে — Dijkstra-র (পর্ব ৪৩) মতো কোনো সমস্যা নেই।

Minimum bottleneck spanning tree

একটি spanning tree-র bottleneck হলো তার সবচেয়ে ভারী edge. যে spanning tree-র bottleneck সবচেয়ে ছোট, সেটি minimum bottleneck spanning tree (MBST). উপমা: বর্ষায় প্রতিটি রাস্তার একটি সর্বোচ্চ পানির গভীরতা; আপনি এমন রাস্তার জাল চান, যার সবচেয়ে খারাপ রাস্তাটিও যতটা সম্ভব কম ডোবে। প্রতিটি MST একটি MBST: ধরুন MST T-এর সবচেয়ে ভারী edge e, আর অন্য একটি spanning tree T′-এর সব edge e-এর চেয়ে হালকা। T থেকে e সরালে একটি cut হয়; T′ connected, তাই T′-এর একটি edge f এই cut পার হয়, আর w(f) < w(e). T − e + f তাহলে T-এর চেয়ে হালকা — বিরোধ। উল্টোটি সত্য নয়: একটি MBST-এর মোট খরচ বেশি হতে পারে। একই যুক্তিতে, MST-তে যেকোনো দুই vertex-এর মধ্যের পথটি তাদের মধ্যে “সবচেয়ে ছোট সর্বোচ্চ edge”-এর পথ (minimax path) — Kruskal-এর ক্রম থেকে এটি বোঝা সহজ।

৮ · MST shortest-path tree নয় — আর বাস্তব প্রয়োগ

সবচেয়ে প্রচলিত ভুল ধারণা: “MST-তে দুই উপজেলার মধ্যের পথই তাদের সবচেয়ে ছোট পথ”. না। MST কমায় মোট কেবলের খরচ; পর্ব ৪৩-এর Dijkstra-র shortest-path tree কমায় একটি উৎস থেকে প্রতিটি vertex-এর দূরত্ব। ছোট একটি প্রতি-উদাহরণ (counterexample) দেখুন — তিনটি উপজেলা S, X, Y:

MST সস্তা (৫ বনাম ৭), কিন্তু তাতে S থেকে Y যেতে ৫, যেখানে সরাসরি পথ ৪. কোনটি দরকার তা প্রশ্নের ওপর নির্ভর করে: কেবল একবার বসানোর খরচ কমাতে হলে MST; প্রতিদিন সদর থেকে প্রতিটি উপজেলায় দ্রুত পৌঁছাতে হলে shortest-path tree. আরেকটি পার্থক্য: সব খরচে ১০ যোগ করলে MST বদলায় না (প্রতিটি spanning tree-তে ঠিক V − 1 টি edge, সবার খরচ সমান বাড়ে), কিন্তু shortest path বদলাতে পারে, কারণ বিভিন্ন পথে edge-এর সংখ্যা আলাদা।

প্রয়োগ ১ — নেটওয়ার্ক নকশা

বিদ্যুৎ, ফাইবার, পানির পাইপ, সার্কিট বোর্ডের তার — সবখানে MST একটি প্রথম খসড়া দেয়। কিন্তু বাস্তবে দুটি সীমা মনে রাখতে হয়। (১) নির্ভরযোগ্যতা: tree-তে প্রতিটি edge একেকটি দুর্বল বিন্দু — একটি কেবল কাটলেই নেটওয়ার্ক দুই ভাগ (পর্ব ৪৬-এর bridge). তাই বাস্তব নকশায় MST-এর ওপর কিছু বাড়তি সংযোগ দিয়ে ring বানানো হয়। (২) নতুন সংযোগ-বিন্দু: মাঝপথে একটি নতুন জংশন বসালে খরচ আরও কমতে পারে — এটি Steiner tree সমস্যা, যা NP-hard (পর্ব ৬৪). মজার ব্যাপার, MST সেখানে একটি ভালো approximation দেয়: Steiner tree-র সর্বোত্তম খরচের ২ গুণের বেশি নয়।

প্রয়োগ ২ — clustering

ধরুন ২০০টি গ্রাহককে তাদের কেনাকাটার মিল অনুযায়ী k টি দলে ভাগ করতে চান, যাতে আলাদা দলের যেকোনো দুজনের মধ্যে দূরত্ব যতটা সম্ভব বেশি থাকে। উত্তর: Kruskal চালান, আর component-এর সংখ্যা k হলেই থামুন। যে দলগুলো রইল, সেগুলোই উত্তর — একে বলে single-linkage clustering. এখানে দলের মধ্যের ন্যূনতম দূরত্ব (spacing) হলো পরের যে edge দুটি দল জুড়ত, তার ওজন; আর cut property-র ধাঁচের একটি exchange যুক্তি দেখায় যে অন্য কোনো k-ভাগে spacing এর চেয়ে বেশি হতে পারে না। সমতুল্যভাবে: পুরো MST বানিয়ে সবচেয়ে ভারী k − 1 টি edge কেটে দিন।

প্রয়োগ ৩ — traveling salesman-এর approximation

একজন বিক্রয়কর্মীকে সব উপজেলা ঘুরে সদরে ফিরতে হবে, মোট পথ সবচেয়ে কম রেখে — traveling salesman problem (TSP), NP-hard. কিন্তু দূরত্ব যদি ত্রিভুজ অসমতা মানে (সরাসরি যাওয়া কখনো ঘুরে যাওয়ার চেয়ে দীর্ঘ নয়), তবে MST দিয়ে দ্রুত একটি ভালো উত্তর পাওয়া যায়: MST-কে DFS ক্রমে ঘুরুন, আর আগে দেখা উপজেলা এড়িয়ে সরাসরি পরেরটিতে যান। যেকোনো ট্যুর থেকে একটি edge সরালে একটি spanning tree পাওয়া যায়, তাই সর্বোত্তম ট্যুরও MST-এর চেয়ে দামি; আর আমাদের ট্যুর MST-এর ২ গুণের বেশি নয়। ফল: সর্বোত্তমের সর্বোচ্চ দ্বিগুণ — একটি ২-approximation. বিস্তারিত পর্ব ৬৬-এ।

৯ · AI-এর যুগে MST — greedy সহজ, প্রমাণ কঠিন

“Kruskal লিখে দাও” — যেকোনো AI সহকারী নিখুঁত দেখতে কোড দেবে, আর ছোট উদাহরণে উত্তরও প্রায়ই ঠিক আসবে। বিপদ লুকিয়ে থাকে তিন জায়গায়: Prim আর Dijkstra-র মধ্যে এক লাইনের পার্থক্য গুলিয়ে ফেলা, DSU-এর বদলে কোনো ভুল “cycle পরীক্ষা”, আর নতুন সমস্যায় অপ্রমাণিত greedy — “সবচেয়ে সস্তা আগে নাও” শুনতে MST-এর মতো হলেও সব সমস্যায় খাটে না।

MST-এর কোডে AI সাধারণত যেসব ভুল করে

MST-এর কোড যাচাইয়ের চেকলিস্ট

• ছোট গ্রাফে Kruskal আর Prim দুটোই চালিয়ে মোট খরচ মিলিয়েছি (edge আলাদা হতে পারে যদি ওজন সমান থাকে, খরচ নয়)
• গৃহীত edge-এর সংখ্যা V − 1 কি না পরীক্ষা করেছি — না হলে গ্রাফ disconnected
• Edge case: V = 1, একই দুই vertex-এর মধ্যে একাধিক edge, self-loop, সব ওজন সমান, ঋণাত্মক ওজন
• V ≤ 7-এর এলোমেলো গ্রাফে সব edge-উপসেট গুনে বের করা উত্তরের সাথে মিলিয়েছি — stress testing
• Prim-এর heap-এ key edge-এর ওজন, দূরত্ব নয় — নিজে লাইনটি পড়ে নিশ্চিত হয়েছি
• AI যে greedy প্রস্তাব করেছে, তার জন্য একটি cut বা exchange যুক্তি চেয়েছি; না পেলে প্রতি-উদাহরণ খুঁজেছি