„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 53. sor: | 53. sor: | ||
}} | }} | ||
===3. Feladat=== | ===3. Feladat (Van megoldás)=== | ||
Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban! | Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban! | ||
| 65. sor: | 65. sor: | ||
'''Mi az a Kruskal algoritmus?'''<br> | '''Mi az a Kruskal algoritmus?'''<br> | ||
A Kruskal algoritmust minimális költségű feszítőfák meghatározására használjuk. A piros-kék algoritmus egyik implementációja. <br> | |||
Lényege, hogy a gráf éleit súlyuk szerint nem csökkenő sorrendbe állítja, majd sorban megpróbálja kékre színezni őket. <br> | |||
Ennek az a feltétele, hogy az újonnan kékre színezendő él beszínezése után se legyen kör a kékre színezett élek által alkotott gráfban. <br> | |||
Ha ez mégis kört eredményezne, úgy az él nem kék, hanem piros lesz.<br> | |||
A kékre színezett élek egy minimális összsúlyú feszítőfát adnak.<br><br> | |||
}} | }} | ||
'''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br> | '''UNIÓ-HOLVAN adatszerkezet definíciója: '''<br><br> | ||
Adott egy véges S halmaz, amelynek egy felosztását (partícióját) akarjuk tárolni. <br> | |||
2 műveletünk van:<br> | |||
UNIÓ(U, V halmazok, amelyek S részhalmazai): S-ből kivesszük az U-t és a V-t, majd hozzáadjuk (unió) U és V unióját. <br><br> | |||
HOLVAN(v pont, v benne van S-ben): Azt az U halmazt adja meg, amelynek v eleme.<br><br> | |||
'''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br> | '''Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:'''<br> | ||
A Kruskal algoritmus lelke az UNIÓ-HOLVAN adatszerkezet. <br> | |||
Kezdetben a gráf minden pontja másik <math>U_i</math> részhalmazban van, tehát minden <math>U_i</math> egy pontot tartalmaz.<br> | |||
Az algoritmus elindul a legkisebb súlyú éleken. <br> | |||
Az élek két végpontjára (v és w) megvizsgálja, hogy HOLVAN(v) egyenlő-e HOLVAN(w)-vel. <br> | |||
Ha igen, akkor egy részhalmazban vannak, kört okoznának => piros él lesz.<br> | |||
Ha nem áll fenn az egyenlőség, akkor a (v,w) kék lesz, a két részhalmazt pedig nyugodtan egyesíthetjük (hozzávehetjük az új élet a kék gráfhoz):<br> | |||
UNIÓ(<math>U_v</math>,<math>U_w</math>). | |||
}} | }} | ||