17. óra
Címkék > Óra

17. óra

(Erben Péter, 2008. 02. 11.)

Minimális összsúlyú feszítőfa

Adott egy gráf, (nemnegatív) élsúlyokkal. Keressük azt a körmentes, minden pontot lefogó részgráfot (feszítőfát), amelynek legkisebb az összsúlya (az éleire írt súlyok összege).

A feladat beceneve a szakirodalomban: MST (Minimum Spanning Tree, minimális feszítő fa).

Kruskal algoritmusa

élek rendezése súly szerint növekvően // e[1], e[2], ..., e[k]
fa := []
komponensek := [[cs[1]], [cs[2]], ..., [cs[n]]]
Ciklus i:=1-től k-ig // az éleken megyünk végig
    Ha e[i] végpontjai különböző komponensekben vannak
    akkor
        fa := fa + e[i]
        a két komponens uniója
    Elágazás vége
Ciklus vége

"Unió-holvan" adatszerkezet

A Kruskal algoritmus két legfontosabb művelete annak ellenőrzése, hogy két csúcs azonos komponensben van-e, illetve a különböző komponensek egyesítése. Egy végtelenül egyszerű adatszerkezettel nagyon gyors megoldást adhatunk mindkét részfeladatra.

A komponenseket irányított fagráfokkal reprezentáljuk, minden komponens "címkéje" a gyökérelem. Az összehasonlításnál a komponensek gyökérelemét kell összehasonlítani. Az egyesítésnél pedig az egyik komponens fáját "bekötjük" a másik gyökere alá.

A fák irányított éleinek tárolásához elég egyetlen apa[] tömb, a gyökér saját magára mutat. Kezdetben mindenki egyelemű komponens:

Ciklus i := 1-től n-ig //egyelemű komponensek
apa[i] := i
Ciklus vége

Egy csúcs komponensének meghatározásához bejárjuk a komponensét reprezentáló gráfot, és a gyökérelem azonosítóját adjuk vissza:

holvan(x):

Ha x != apa[x]
akkor holvan := holvan(apa[x])
különben holvan := x
Elágazás vége

Az unio is egyszerű:

unio(x,y):

apa[y] := x

Hatékonyság

Sokat gyorsít az algoritmuson, ha a komponensek fáinak mélységét korlátozni tudjuk. Erre két ismert módszer is van: (a) unio-nál a kisebb mélységű fát kötjük a nagyobb alá; (b) keresésnél "útösszenyomást" végzünk, ami azt jelenti, hogy a bejárt csúcsokat mind átkötjük közvetlenül a gyökér alá.

Feladat

Áramszünet