Ceanglaíonn crann spréachta íosmhéide (MST) gach gné de ghraf ualaithe agus ceangailte le meáchan iomlán íosmhéide na n-imill agus gan timthriallta. Is iad Kruskal agus Prim an dá algartam gréannach clasaiceach.
Sórtáil gach iomarc de réir meáchain; cuir an iomarc is saoire leis nach ndéanann timthriall.
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
Tosú ó aon ghné; go leanúnach cuir an iomarc is saoire a fhágann an crann reatha.
| Kruskal | Prim | |
|---|---|---|
| Cur chuige | imill a shórtáil + union-find | fás ó nód + heap |
| Am | O(E log E) | O(E log V) |
| Is fearr do | graif ghann | graif dhéanna |
Úsáid MST do dhearadh líonra — cábla a leagan, píobáin uisce, grúpáil. Tá an dá cheann gréannach agus fíoraithe go raibh siad i bhfeighil anseo. Tá gá ag Kruskal do union-find chun timthriallta a sheachaint go héifeachtach.
Laghdaíonn MST an costas a bheith ceangailte ar an uile rud — infheidhmeannach go díreach ar bhonneagar agus leagan amach líonra.
Is cás geal a bhíonn ann ina bhfuil an greannach fíoraithe go raibh sé i bhfeighil, ag neartú smaoineamh roghnaithe gréannach.
Bronntanann Kruskal freisin union-find, struchtúr le raon algoritmach leathan.