Kruskal-algoritmus

Magyar

(matematika, gráfelmélet, algoritmusok) A Kruskal-algoritmus egy súlyozott gráfokat feldolgozó mohó algoritmus. Ha a gráf összefüggő, akkor minimális feszítőfa megalkotására szolgál, ha nem, akkor minimális feszítőerdőt hoz létre. Lépések:
- Válasszuk ki a legkisebb súlyú élt.
- Amennyiben az él a részgráfhoz való hozzáadása kört alkot, dobjuk azt el.
- Ha van még nem vizsgált él, folytassuk az előző lépésekkel.

Tartalom