Kruskal algoritmus

- rendeljünk egy gráf éleihez súlyokat, nemnegatív valós számokat
- jelöljük s(e)-vel az e-hez rendelt súlyt
- adjunk algoritmust, amely megkeresi a minimális súlyú feszítőerdőt G-ben

- algoritmus [Kruskal]:

- az éleket egyesével választjuk ki a következők szerint
- először válasszuk ki a gráfból a legkisebb súlyú élek egyikét
- tegyük fel, hogy már kiválasztottunk néhány élet
- ekkor válasszuk a legkisebb súlyú olyan élek egyikét, amely nem alkot kört az eddig már kiválasztottakkal
- ha ilyen nincs, megállunk, ha van, akkor ezt az eljárást ismételjük

- a Kruskal algoritmus nyilván egy mohó algoritmus a legkisebb súlyú feszítőerdő megkeresésére

- a mohó algoritmus azonban más feladatok, pl. a legkisebb súlyú kör megkeresésére vagy páros gráfban a max. párosítás megkeresése esetén nem feltétlenül ad jó megoldást