Mti wa kuunganisha kwa kiwango cha chini (MST) unaunganisha wima zote za grafu iliyozani na iliyounganishwa kwa jumla ya uzani wa kingo wa chini kabisa na hakuna mizunguko. Kruskal na Prim ni algorithms mbili za greedy za kawaida.
Panga kingo zote kwa uzani; ongeza kingo yenye bei ya chini zaidi ambayo haitengenezi mizunguko.
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
Jianza kutoka kwa kimo chochote; rudia kuongeza kingo yenye bei ya chini zaidi inayoondoka mti wa sasa.
| Kruskal | Prim | |
|---|---|---|
| Njia | panga kingo + union-find | kuza kutoka kwa nodi + heap |
| Wakati | O(E log E) | O(E log V) |
| Nzuri sana kwa | grafu zenye kingo chache | grafu nyingi za kingo |
Tumia MST kwa muundo wa mtandao — kulaza kebo, mabomba ya maji, kuweka vikundi. Zote mbili ni greedy na nadhifu optimal hapa. Kruskal inahitaji union-find ili kutofautiana na mizunguko kwa ufanisi.
MST inapunguza gharama ya kuunganisha kila kitu — inaweza kutumika moja kwa moja katika miundombinu na muundo wa mtandao.
Ni kesi safi ambapo greedy ni nadhifu optimal, ikiinza sababu ya greedy-choice.
Kruskal pia inaonyesha union-find, muundo una matumizi mapana ya algorithmic.