Kruskalen algoritmoa

**Kruskal**-en **algoritmoa** grafoen teoriako algoritmo bat da; grafo konexu eta pisudun batean zuhaitz estaltzaile minimo bat aurkitzeko. Hau da, ertzen azpi-multzo bat bilatzen du, zuhaitz bat osatuz, non grafoko erpin guztiak sartzen diren eta zuhaitzeko ertzen guztien baturaren balioa minimoa den. Grafua konexua ez bada, baso hedatzaile minimo bat bilatzen du.

Algoritmo hau Joseph Kruskalen izena du, lehenengoz 1956an argitaratu zuelako  eta handik gutxira berraurkitu zuen Loberman & Weinbergerrek (1957).  Kruskalena bezalako beste algoritmo batzuk dira Primen algoritmoa, borratzaile alderantzizko algoritmoa eta Boruvkaren algoritmoa.

## Algoritmoa 
Kruskalen algoritmoa algoritmo irenskor baten adibide bat da, eta honela funtzionatzen du:

* B baso bat sortzen da (zuhaitz multzo bat), non grafoaren erpin bakoitza zuhaitz bereizi bat den
* Grafoaren ertz guztiak bilduko dituen C multzoa sortzen da. C hutsa ez den bitartean:
** C pisuko gutxieneko ertz bat kendu
** Ertz horrek bi zuhaitz desberdin lotzen baditu, basoari gehitzen zaio, bi zuhaitzak zuhaitz bakar batean konbinatuz.
** Bestela, ertz hori baztertu egingo da.

Algoritmoa amaitzean, basoak osagai bakarra du, grafoaren hedapen minimoko zuhaitz bat osatzen duena.

Gutxieneko hedapen-zuhaitz batean, zer betetzen da:

* Zuhaitzaren ertz kopurua nodo kopurua ken bat da (1).

### Pseudokodigoa 
```
funtzioa Kruskal(G)
    // G = (V, E), pisudun grafo zuzendugabea

    V[G]-ko nodo bakoitzerako v:
        sortu multzo berria C(v) ← {v}

    Q ← G-ren ertz guztiak, pisuaren arabera igoeran ordenatuak

    T ← Ø     // hedapen-minimoko zuhaitza (MST)

    bitartean |T|  self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

# Kruskal algoritmoa
def kruskal(n, ertzak):
    """
    n: nodo kopurua (0...n-1)
    ertzak: Edge objektuen zerrenda
    """
    ertzak.sort()  # pisuaren arabera ordenatu
    uf = UnionFind(n)
    T = []  # hedapen-minimoko zuhaitza (MST)

    for e in ertzak:
        if uf.find(e.u) != uf.find(e.v):
            T.append(e)
            uf.union(e.u, e.v)

        if len(T) == n - 1:
            break

    return T
```

## Algoritmoaren konplexutasuna 
*m* grafoaren ertz kopurua eta *n* erpin kopurua izanda, Kruskalen algoritmoak O(*m* log *m*) konplexutasuna erakusten du, edo, baliokide gisa, O (*m* log *n*), datu sinpleen egituren gainean exekutatzen denean. Gauzatze-denborak baliokideak dira, arrazoi hauengatik:

* m gehienez *n*² da eta log *n*² = 2log*n* da O(log n).
* isolatutako erpinak alde batera utzita, horiek osatzen baitute hedapen minimoko zuhaitzaren osagai propioa, n ≤ 2*m*; beraz, log *n* da O(log *m*).
thumb|Kruskal algoritmoak zuhaitz estaltzaile minimo bat lortzen du.
Konplexutasun hori honela lor daiteke: lehenik eta behin, ertzak pisuaren arabera ordenatzen dira, konparazio bidezko antolamendu bat erabiliz (comparison sort); horri esker, "C-ren gutxieneko pisuko ertz bat ezabatzea" denbora konstantean exekutatzen da. Hurrengoa da datu-egitura bat erabiltzea multzo disjuntuetarako, erpinak  zein osagaitan dauden kontrolatzeko. Beharrezkoa da O(*m*) eragiketen ordena egitea, ertz bakoitzeko bi bilaketa-eragiketa baitaude eta, beharbada, multzoen lotura bat. Are gehiago, lerrunen araberako loturak dituen multzo disjuntuei buruzko datu-egitura sinple batek O(*m* log *n*) hizkian aipatutako eragiketak egin ditzake. Beraz, konplexutasun osoa O(*m* log *m*) = O(*m* log *n*) da.

Ertzak ordenatuta badaude edo denbora lineal batean ordenatu badaitezke (adibidez, kontuen araberako ordenamenduaren bidez edo Radix ordenamenduaren bidez), algoritmoak multzo disjuntu konplexuagoen datu-egiturak erabil ditzake O(*m* α(*n*) ordenaren garaian exekutatzeko, non α Ackermannen funtzioaren alderantzizkoa den (hazkunde oso motela du).

## Adibidea 
## Ikusi ere 
* Dijkstraren algoritmo

## Erreferentziak 
## Kanpo estekak 
* Artikuluaren adibiderako datuak
* Kruskal algoritmoa — adibidea eta C++ programa
* Kruskal algoritmoa — C++ kodea zenbaki ausazkoekin
* Kruskal algoritmoa — Python kodea azalpenarekin
* Kruskal algoritmoa — C kodea azalpen eta adibidearekin
* Kruskal algoritmoaren implementazioa — grafo batean MST lortzeko