Prim, Kruskal ve disjoint set union

Spanning tree bütün düğümleri bağlayan, cycle içermeyen V−1 kenarlı yapıdır. MST toplam kenar maliyetini minimize eder; bir root'tan her düğüme en kısa yolu garanti etmez. Bağlantısız graf için minimum spanning forest vardır. Negatif kenarlar MST'yi bozmaz.

Cut property, bir kesiti geçen en ucuz kenarın uygun bir MST'ye güvenle eklenebileceğini söyler. Prim mevcut ağaca en ucuz kesit kenarını ekler. Kruskal bütün kenarları ağırlıkla sıralar ve farklı bileşenleri bağlayanları seçer. Eşit ağırlıklarda birden fazla MST olabilir.

DSU find ile temsilci, union ile bileşen birleştirme sunar. Path compression ve union by rank/size beraber uzun işlem dizilerinde amortize O(α(n)) verir; tam O(1) demek teknik olarak doğru değildir. DSU arbitrary silmeyi aynı kolaylıkla desteklemez. Rollback DSU gibi varyantlar compression politikasını farklı kurar.

class DSU:
    def __init__(self, n): self.p=list(range(n)); self.size=[1]*n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        a,b = self.find(a), self.find(b)
        if a == b: return False
        if self.size[a] < self.size[b]: a,b=b,a
        self.p[b]=a; self.size[a]+=self.size[b]
        return True
d=DSU(3)
assert d.union(0,1) and d.union(1,2) and not d.union(0,2)