Kruskal's algorithm

Kruskal's algorithm (tsz. Kruskal's algorithms)

1. (informatika) Kruskal-algoritmus

A Kruskal-algoritmus egy greedy módszer a minimális feszítőfa (Minimum Spanning Tree, MST) előállítására összefüggő, súlyozott, irányítatlan gráfokban. Célja, hogy az összes csúcsot lefedje úgy, hogy a kiválasztott élek súlyösszege minimális legyen, miközben körök (ciklusok) létrejöttét elkerüli.

2. Az algoritmus ötlete

1. Élsorrend kialakítása
   • Rendezzük az összes élt nemcsökkenő sorrendbe a súlyuk szerint.
2. Élek felvétele
   • Sorban végigmegyünk a legkisebb súlyú éltől a nagyobbak felé, és minden élhez eldöntjük, hogy hozzáadható-e anélkül, hogy ciklust hozna létre.
3. Cikluselkerülés
   • Használunk egy egyesítő–kereső (Union-Find vagy disjoint-set) adatszerkezetet, ami két műveletet támogat:
     • Find(u): megtalálja u komponensének „gyökér” képviselőjét.
     • Union(u, v): összefűzi (egyesíti) két komponens képviselőit.
   • Minden él ${\textstyle (u,v)}$ vizsgálatakor ha Find(u) != Find(v), akkor az él nem zár ciklust ⇒ felvesszük az MST-be, és Union(u,v)-vel egyesítjük a komponenseket.

Az iteráció addig tart, míg az MST-ben ${\textstyle |V|-1}$ él nem gyűlt össze (ahol ${\textstyle |V|}$ a csúcsok száma).

3. Pseudokód

Kruskal(G, w):
    // G = (V, E) összefüggő, súlyozott, irányítatlan gráf
    T = ∅                         // az MST éleinek halmaza
    rendezd növekvően E-t w szerint
    inicializáld a disjoint-setet V elemekkel

    for minden (u, v) ∈ E, súly szerint:
        if Find(u) ≠ Find(v):
            T = T ∪ {(u, v)}
            Union(u, v)
        if |T| == |V| - 1:
            break

    return T

4. Idő- és helykomplexitás

• Élsorrendezés: ${\textstyle O(|E|\log |E|)}$. Mivel ${\textstyle |E|}$ általában nagyobb, ezt tekintjük dominánsnak.

• Disjoint-set műveletek: Ha útösszevonással (union by rank) és útkompresszióval (path compression) valósítjuk meg, akkor egy Find vagy Union amortizált ${\textstyle O(\alpha (|V|))}$, ahol ${\textstyle \alpha }$ az inverz Ackermann-függvény (gyakorlatilag konstans). Összesen legfeljebb ${\textstyle |E|}$ Find és ${\textstyle |V|}$ Union hívás ⇒ ${\textstyle O(|E|\alpha (|V|))}$.

• Összesen:

  $${\displaystyle O{\bigl (}|E|\log |E|+|E|\alpha (|V|){\bigr )}=O(|E|\log |E|).}$$

• Helyigény:

  • A disjoint-set tömbök: ${\textstyle O(|V|)}$.
  • Az élsorrendezés és az MST tárolása: ${\textstyle O(|E|)}$.

5. Példa Legyen a következő gráf élekkel és súlyokkal:

    1       4
A ——— B ——— C
| \     |
2  3    5
|     \ |
D ———— E
    6

Élek:

(A,B)=1, (A,D)=2, (A,E)=3, (B,C)=4, (B,E)=5, (D,E)=6

1. Rendezés súly szerint: ${\textstyle (A,B)=1,\ (A,D)=2,\ (A,E)=3,\ (B,C)=4,\ (B,E)=5,\ (D,E)=6}$

2. Disjoint-set inicializálás: minden csúcs külön komponens.

3. Élek feldolgozása:

   • (A,B)=1: külön komponens ⇒ felvesszük, egyesítjük A és B.

   • (A,D)=2: A és D külön ⇒ felvesszük, egyesítjük.

   • (A,E)=3: A (és B, D) külön E-től ⇒ felvesszük, egyesítjük.

   • (B,C)=4: B (koalícióban A,D,E) külön C-től ⇒ felvesszük, egyesítjük.

   • Ezt követően már ${\textstyle |V|-1=4}$ él gyűlt össze, MST kész:

     $${\displaystyle \{(A,B),(A,D),(A,E),(B,C)\}.}$$

   • Az élek (B,E) és (D,E) kimaradnak, mert egységkomponensekbe esnének.

6. Python-implementáció

class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, v):
        if self.parent != v:
            self.parent = self.find(self.parent)
        return self.parent

    def union(self, u, v):
        ru, rv = self.find(u), self.find(v)
        if ru == rv:
            return
        # union by rank
        if self.rank < self.rank:
            self.parent = rv
        elif self.rank > self.rank:
            self.parent = ru
        else:
            self.parent = ru
            self.rank += 1

def kruskal(vertices, edges):
    """
    vertices: iterable csúcsok
    edges: lista 
    visszatér: lista az MST élekkel (u, v, w)
    """
    # 1. rendezés
    edges = sorted(edges, key=lambda x: x)
    ds = DisjointSet(vertices)
    mst = 

    # 2. élek hozzáadása
    for u, v, w in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, w))
            if len(mst) == len(vertices) - 1:
                break
    return mst

# Példa használat
verts = 
eds = [
    ('A','B',1), ('A','D',2), ('A','E',3),
    ('B','C',4), ('B','E',5), ('D','E',6)
]
print("MST:", kruskal(verts, eds))

7. Alkalmazások

• Hálózattervezés: telekommunikációs, elektromos hálózatok kiépítése minimális költséggel.
• Klaszterelemzés: adatok csoportosítása feszítőfa alapján, például hierarchikus klaszterezésben.
• Közlekedési hálózatok: út- vagy vasúthálózat tervezése.
• Biológiai fák: filogenetikai fák költségalapú rajzolása.

8. Összefoglalás A Kruskal-algoritmus egyszerű, de hatékony girbegurba eljárás a minimális feszítőfa megtalálására. A kulcs a súly szerinti élsorrendezés és a disjoint-set adatszerkezet használata a ciklusok elkerüléséhez. ${\textstyle O(|E|\log |E|)}$ időkomplexitása miatt széles körben alkalmazható mérsékelt és nagy méretű gráfokban.

• Kruskal's algorithm - Szótár.net (en-hu)
• Kruskal's algorithm - Sztaki (en-hu)
• Kruskal's algorithm - Merriam–Webster
• Kruskal's algorithm - Cambridge
• Kruskal's algorithm - WordNet
• Kruskal's algorithm - Яндекс (en-ru)
• Kruskal's algorithm - Google (en-hu)
• Kruskal's algorithm - Wikidata
• Kruskal's algorithm - Wikipédia (angol)