Kruskal's algorithm

Angol

Főnév

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

(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

Élsorrend kialakítása
- Rendezzük az összes élt nemcsökkenő sorrendbe a súlyuk szerint.
É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.
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:

$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

Rendezés súly szerint: ${\textstyle (A,B)=1,\ (A,D)=2,\ (A,E)=3,\ (B,C)=4,\ (B,E)=5,\ (D,E)=6}$
Disjoint-set inicializálás: minden csúcs külön komponens.
É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:
  
  $\{(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] != v:
            self.parent[v] = self.find(self.parent[v])
        return self.parent[v]

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

def kruskal(vertices, edges):
    """
    vertices: iterable csúcsok
    edges: lista [(u, v, w), ...]
    visszatér: lista az MST élekkel (u, v, w)
    """
    # 1. rendezés
    edges = sorted(edges, key=lambda x: x[2])
    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 = ['A','B','C','D','E']
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.

További információk

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)