Minimum Spanning Tree — அடிப்படை

Minimum Spanning Tree — வரைபடத்தில் முக்கியமான நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வரைபடம், சமூக வலை, சார்பு அமைப்பு — தலைகோடுகள்/விளிம்புகள் மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

வெட்டு சொத்து; Kruskal+UF; Prim≈Dijkstra.

Pythonில் முயற்சி செய்வோம்

class UnionFind:
    def __init__(self, n: int) -> None:
        self.p = list(range(n))
        self.r = [0] * n

    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True


uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.find(0), uf.find(3))

பொதுவான தவறுகள்

• துண்டு வரைபடம்.
• வரிசை மறப்பு.

முக்கிய பாடங்கள்

• தோராயம் அடிப்படை.
• தனித்துவ எடை.