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| < |V| - 1 eta EZ Q.hutsa() egin
        (u, v) ← Q.ateraMin()     // pisu txikieneko ertzaren aukeraketa

        bada C(u) ≠ C(v) orduan
            Gehitu (u, v) ertza T-ra
            Batu C(u) eta C(v) multzo bakarrean   // Merge/Union

    itzuli T

 Python Kodea 
# Ertz baten egitura
class Edge:
    def __init__(self, u, v, pisua):
        self.u = u
        self.v = v
        self.pisua = pisua

    def __lt__(self, other):
        return self.pisua < other.pisua

# Union-Find (Disjoint Set) egitura
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX == rootY:
            return

        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > 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² = 2logn da O(log n).
 isolatutako erpinak alde batera utzita, horiek osatzen baitute hedapen minimoko zuhaitzaren osagai propioa, n ≤ 2m; beraz, log n da O(log m).
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 
+Fitxategi:Prim Algorithm 0.svgHau jatorrizko grafoa da. Ertzetako zenbakiek haien pisua adierazten dute. Ertzetako bat ere ez dago nabarmenduta.Fitxategi:Kruskal Algorithm 1.svgAD eta CE ertzik laburrenak dira, 5 pisukoak, eta AD arbitrarioki aukeratu da; beraz, nabarmendu egiten da.Fitxategi:Kruskal Algorithm 2.svgHala ere, orain CE da zikloak osatzen ez dituen ertzik txikiena, 5 pisukoa, eta, beraz, bigarren ertz gisa nabarmentzen da.Fitxategi:Kruskal Algorithm 3.svgHurrengo ertza, 6 pisuko DF, metodo bera erabiliz nabarmendu da.Fitxategi:Kruskal Algorithm 4.svgHurrengo ertz txikienak AB eta BE dira, biak 7 pisuarekin. AB arbitrarioki aukeratzen da, eta nabarmendu egiten da. BD ertza gorriz nabarmentzen da, aukeratu izan balitz ABD zikloa osatuko lukeelako.Fitxategi:Kruskal Algorithm 5.svgProzesuak ertzak markatzen jarraitzen du, BE 7 pisuarekin. Beste ertz asko gorriz markatzen dira urrats honetan: BC (EBZ zikloa osatuko luke), DE (DEBA zikloa osatuko luke), eta FE (FEBAD zikloa osatuko luke).Fitxategi:Kruskal Algorithm 8a.svgAzkenik, prozesua 9 pisuko EG ertzarekin amaitzen da, eta gutxieneko zuhaitz hedatua aurkitu da, 39ko guztizko pisuarekin.

 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

Kategoria:Algoritmoak
Kategoria:Grafo teoria