SHPORA.net :: PDA

[ Back ]

Toesepuu



Sidusa lihtgraafi (V, E) toesepuuks e. toeseks (spanning tree) nim. sidusat atsüklilist graafi (V, T), milles T on E alamhulk.



Kõik tipud on samad, servi on eemaldatud nii, et kaoksid tsüklid, aga sidusus säiliks. Toes ei ole üldjuhul üheselt määratud.



Kui servadel on mittenegatiivsed kaalud, siis pakub huvi niisuguse toese leidmine, mille kogukaal oleks minimaalne (kõigi toespuude hulgast).



Kruskali algoritm: järjestada servad kaalude järgi mittekahanevalt ning valida selle alusel järjekordne serv toesesse juba olemasolevate osapuude ühendamiseks (kui moodustub tsükkel, siis seda serva ei võeta). Alt-üles (alguses on üksikud tipud, lõpuks peavad kõik tipud esinema omas sidususkomponendis), ahne strateegia (valitakse hetkel parim tee).



Primi algoritm: töötatakse antud lähtetipust laiuti sarnaselt Dijkstra algoritmiga (toesesse valitakse hetkejätkudest minimaalse kaaluga serv, meeles peetakse kaalu ja eellast, vajadusel parandatakse eellast teel allikast antud tipuni).