Algoritmul Kruskal - arbore de valoare minima

Simulare pas cu pas. La fiecare generare se schimba pozitiile varfurilor, structura grafului si costurile. Fiecare cutie reprezinta o componenta conexa. O muchie este acceptata numai daca extremitatile ei se afla in cutii diferite. Dupa acceptare, cele doua cutii se reunesc.

Graful ponderat

NeexaminataIn examinareAcceptataRespinsa (circuit)

Cutiile componentelor conexe

La inceput, fiecare varf este singur intr-o cutie. Daca doua varfuri sunt deja in aceeasi cutie, muchia dintre ele ar inchide un circuit.

Explicatia pasului

Cum functioneaza verificarea circuitelor?

Fiecare cutie contine varfurile legate deja prin muchiile acceptate. Pentru muchia (u,v):

Cutii diferite: acceptam muchia, adunam costul si unim cutiile. Aceeasi cutie: respingem muchia, deoarece exista deja un drum intre u si v, deci adaugarea ei ar forma un circuit.

Muchiile sunt examinate in ordine crescatoare a costului. Algoritmul se opreste cand sunt acceptate n - 1 muchii.