Minimális költségű feszítőfa probléma: Adott egy G összefüggő gráf és egy c:E(G)->R>0 költségfüggvény. Ez költségfüggvény kitejeszthető az élhalmazokra (egy élhalmaz költsége elemei költségének összege) és részgráfokra (egy részgráf költsége élhalmazának költsége). Keresünk minimális költségű feszítőfát. Természetesen olyan feszítő részgráf keresése a cél, amely az összes csúcsot összeköti, azaz összefüggő. A minimalizálás vezet arra, hogy a feszítőfák között keressünk.
Ismert a Kruskal-algoritmus:
Inicializálás: Legyen A az üreshalmaz, az eddig kiválasztott élek halmaza.
Algoritmusunk ezt növeli addig, amíg egy feszítőfa élhalmazává
nem válik.
Rendezési lépés:
Rakjuk sorba az éleket költségeik szerint, a kisebb költségű
elemek kerüljenek előre.
Beválasztási lépések:
Az első nem vizsgált élre nézzünk meg, hogy A-hoz hozzáadva
körmentes élhalmazhoz jutunk-e. Ha igen, akkor növeljük A-t.
Ha nem, akkor A maradjon.
Ha még van nem vizsgált él, akkor újra végezzük el a beválasztási
lépést. Ha az összes él vizsgált, akkor álljunk le.
Az aktuális A az algoritmus outputja.
A fenti magas szintű leírás még sok gondolkozni valót hagy annak, aki implementálni szeretné Kruskal algoritmusát. Ehhez néhány ötlet.