10.6. Minimális költség ű feszítőfa

Legyen G = (V,E) egy gráf. A G gráf egy körmentes, összefüggő F = (V,E0) részgráfja a G gráf feszítőfája. A G gráf F feszítőfája minimális költségű, ha a benne szereplő élek súlyának az összege minimális G összes feszítőfája közül. Kruskal algoritmusa sorra veszi az összes élt, s ha a két él különböző komponensekhez tartozik, összekapcsolja a komponenseket. Megfelelő adatszerkezet használatával az algoritmus bonyolultsága O(E ln(E)).

Procedure KRUSKAL-FESZÍTő(G,súly) 
Input: G gráf 
Eredmény: Az A tartalmazza a feszítőfát 
1  A = ∅
2  forall the v ∊ V do 
3     HALMAZT-KÉSZÍT (v) 
4  endfall
5  forall the (u, v) ∊ E (Súly szerint növekvő sorrendben!) do 
6     if HALMAZT-KERES(u)!=HALMAZT-KERES(v) then 
7        A = A ⋃ {(u, v)} 
8        EGYESÍT (u,v) 
9     endif 
10 endfall 

Prim algoritmusában felhasználunk egy kulcs segédtömböt, amely azt adja meg, hogy milyen messze vannak megadott gyökérből kinőtt fától ebben a fában még nem szereplő csúcsok. (Ezt a távolságot kezdetben végtelenre állítottuk.) Majd sorra átemeljük a fába a legközelebbi csúcsot. Természesen ekkor újra be kell állítani ezen csúcs szomszédjainak távolságát, s a távolsághoz tartozó szülőt. Az algoritmus bonyolultsága kupacok használatával O(E ln(V )), ám más, speciális adatszerkezettel O(E + V ln(V ))-re csökkenthető.

Procedure PRIM-FESZÍTő(G,súly,r) 
Input: G gráf, súly az élek súlyozása, r kezdőcsúcs 
Eredmény: r gyökerű faként állítja elő a feszítőfát 
11 Q = V 
12 forall the v ∊ Q do 
13    v.kulcs = ∾ 
14 endfall
15 r.kulcs = 0 
16 r.apa = Nil 
17 while Q != ∅ do 
18    u = KIVESZ-MIN(Q) 
19    forall the v ∊ Adj(u) do 
20       if v ∊ Q and súly(u, v) ≤ v.kulcs then 
21          v.apa = u 
22          v.kulcs = súly(u, v) 
23       endif 
24    endfall 
25 endw