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
fa := []
komponensek := [[cs[1]], [cs[2]], ..., [cs[n]]]
Ciklus i:=1-től k-ig
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
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
