মিনিমাম স্প্যানিং ট্রি — ক্রুসকাল ও প্রিম, প্রমাণসহ

import random
import heapq
from itertools import combinations

# ---------- সরল ইউনিয়ন-ফাইন্ড (পাথ-কম্প্রেশন/র‍্যাংক ছাড়া -- পূর্ণাঙ্গ সংস্করণ M10/L46-এ) ----------
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False    # ইতিমধ্যে একই কম্পোনেন্টে -- যোগ করলে চক্র হতো
        self.parent[ra] = rb
        return True

def kruskal(n, edges):
    # edges: (u, v, w) ট্রিপলের লিস্ট
    uf = UnionFind(n)
    total = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if uf.union(u, v):
            total += w
    return total

def build_adj(n, edges):
    adj = {i: [] for i in range(n)}
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    return adj

def prim(n, adj):
    visited = [False] * n
    total = 0
    heap = [(0, 0)]   # (ওজন, ভার্টেক্স) -- ভার্টেক্স 0 থেকে শুরু
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for v, wt in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (wt, v))
    return total

def is_connected(n, edge_list):
    if n == 0:
        return True
    adj = {i: [] for i in range(n)}
    for u, v, w in edge_list:
        adj[u].append(v)
        adj[v].append(u)
    seen = {0}
    stack = [0]
    while stack:
        node = stack.pop()
        for nb in adj[node]:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    return len(seen) == n

random.seed(3)
mismatches = 0
trials = 20
for trial in range(trials):
    n = random.randint(4, 12)
    nodes = list(range(n))
    random.shuffle(nodes)
    # প্রথমে একটি র‍্যান্ডম স্প্যানিং পথ দিয়ে গ্র্যাফ কানেক্টেড আছে তা নিশ্চিত করা
    edges = [(nodes[i], nodes[i + 1], random.randint(1, 20)) for i in range(n - 1)]
    # তারপর কিছু অতিরিক্ত র‍্যান্ডম এজ যোগ করা
    extra_pairs = list(combinations(range(n), 2))
    random.shuffle(extra_pairs)
    extra_count = random.randint(0, len(extra_pairs) // 2)
    for u, v in extra_pairs[:extra_count]:
        edges.append((u, v, random.randint(1, 20)))

    assert is_connected(n, edges)
    k_total = kruskal(n, edges)
    p_total = prim(n, build_adj(n, edges))
    if k_total != p_total:
        mismatches += 1
        print("MISMATCH:", n, edges, k_total, p_total)

print(f"মোট র‍্যান্ডম গ্রাফ: {trials}, ক্রুসকাল বনাম প্রিমের মধ্যে অমিল: {mismatches}")

def brute_force_mst(n, edges):
    # সত্যিকারের এক্সহস্টিভ সার্চ: |V|-1 এজের প্রতিটি কম্বিনেশন, সংযুক্ততা যাচাই করে সর্বনিম্ন ওজন খোঁজা
    best = None
    for subset in combinations(edges, n - 1):
        if is_connected(n, subset):     # n ভার্টেক্স, n-1 এজ, সংযুক্ত => নিশ্চিতভাবে একটি স্প্যানিং ট্রি
            weight = sum(w for _, _, w in subset)
            if best is None or weight < best:
                best = weight
    return best

random.seed(3)
tiny_mismatches = 0
tiny_trials = 15
for trial in range(tiny_trials):
    n = random.randint(3, 6)
    nodes = list(range(n))
    random.shuffle(nodes)
    edges = [(nodes[i], nodes[i + 1], random.randint(1, 10)) for i in range(n - 1)]
    extra_pairs = list(combinations(range(n), 2))
    random.shuffle(extra_pairs)
    k_extra = random.randint(0, min(3, len(extra_pairs)))
    for u, v in extra_pairs[:k_extra]:
        edges.append((u, v, random.randint(1, 10)))

    assert is_connected(n, edges)
    k_total = kruskal(n, edges)
    p_total = prim(n, build_adj(n, edges))
    b_total = brute_force_mst(n, edges)   # সম্পূর্ণ স্বতন্ত্র এক্সহস্টিভ সার্চ

    if not (k_total == p_total == b_total):
        tiny_mismatches += 1
        print("TINY MISMATCH:", n, edges, "kruskal=", k_total, "prim=", p_total, "brute=", b_total)

print(f"টাইনি গ্রাফ ({tiny_trials}টি, n<=6): ক্রুসকাল/প্রিম বনাম ব্রুট-ফোর্সের মধ্যে অমিল: {tiny_mismatches}")

# একটি নির্দিষ্ট উদাহরণ বিস্তারিত দেখানো
example_edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2)]
example_n = 5
print("\nউদাহরণ গ্রাফ (u, v, weight):", example_edges)
print("  ক্রুসকাল মোট ওজন:      ", kruskal(example_n, example_edges))
print("  প্রিম মোট ওজন:         ", prim(example_n, build_adj(example_n, example_edges)))
print("  ব্রুট-ফোর্স মোট ওজন:   ", brute_force_mst(example_n, example_edges))