A minimális feszítőfa (MST) összeköti a súlyozott, összekapcsolt gráf összes csúcsát a minimális teljes élsúllyal és ciklusok nélkül. A Kruskal és a Prim két klasszikus mohó algoritmus.
Rendezz összes élt súly szerint; add hozzá a legolcsóbb élt, amely nem okoz ciklust.
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
Kezd bármelyik csúcsból; ismételten add hozzá az aktuális fát elhagyó legolcsóbb élt.
| Kruskal | Prim | |
|---|---|---|
| Megközelítés | élek rendezése + union-find | növesztés csomópontból + kupac |
| Idő | O(E log E) | O(E log V) |
| Legjobb | ritka gráfokhoz | sűrű gráfokhoz |
Használd az MST-t a hálózattervezéshez — kábel fektetés, vízcsatorna, klaszterezés. Mindkettő mohó és itt bizonyítottan optimális. Kruskalnak union-find kell a ciklusok hatékony elkerüléséhez.
Az MST minimalizálja mindenki összekapcsolásának költségét — közvetlenül alkalmazható az infrastruktúrára és a hálózat elrendezésére.
Ez egy tiszta eset, ahol a mohó megközelítés bizonyítottan optimális, erősítve a mohó-választás logikáját.
A Kruskal szintén bemutatja az union-find-et, egy szerkezetet széles algoritmikus hatókörrel.
IT interjúkérdések gyűjteménye részletes válaszokkal — Juniortól Seniorig.
Adományozás