Arborele parțial de cost minim (Kruskal)
Un campus universitar are 5 clădiri și vrea să le lege pe toate la rețeaua de fibră optică. Fiecare cablu posibil între două clădiri are un cost. Nu e nevoie de toate cablurile: ajunge ca orice clădire să poată comunica cu oricare alta, eventual prin intermediari. Care e costul minim? Răspunsul este arborele parțial de cost minim, iar algoritmul lui Kruskal îl construiește cu o sortare și Union-Find.
Problema
Primești un graf neorientat ponderat și conex cu n noduri. Un arbore parțial (*spanning tree*) este o submulțime de muchii care leagă toate nodurile fără cicluri: are exact n - 1 muchii. Îl vrem pe cel cu suma costurilor minimă (MST).
muchii = [('A', 'B', 4), ('A', 'C', 1), ('B', 'C', 2), ('C', 'D', 5), ('B', 'D', 3)]
ordonate = sorted(muchii, key=lambda m: m[2]) # după cost, crescător
for a, b, cost in ordonate:
print(a, '-', b, ':', cost) Scrie funcția kruskal(n, muchii) pentru nodurile 0 .. n-1, cu muchii (a, b, cost). Returnează tuplul (cost total, muchiile alese în ordinea alegerii), folosind muchiile sortate după cost și clasa UnionFind dată. Dacă graful nu poate fi lega…
- Parcurge sorted(muchii, key=lambda m: m[2]).
- Dacă uf.uneste(a, b) întoarce True, adaugi costul și muchia la rezultat.
- La final, dacă ai mai puțin de n - 1 muchii, întoarce (-1, []).
- Trebuie să apară Cost total: 8, apoi cablurile 1-2, 1-3, 3-4, 0-2 și rezultatele celorlalte teste.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan