Uvazujme souvisly neohodnoceny graf. Pak libovolna podmnozina hran, ktera spolecne s vrcholy grafu tvori souvisly acyklicky graf, se nazyva kostra grafu (spanning tree). Pokud uvazujeme ohodnoceny graf, pak muzeme definovat take minimalni kostru grafu (minimum spanning tree) jako kostru, ktera ma nejmensi soucet vah svych hran. I minimalnich koster grafu muzeme mit ovsem vice - pokud existuje vice koster se stejnym souctem vah svych hran.

      Prirozene nas zajima, jak takovou kostru resp. minimalni kostru najit. Tuto ulohu vyresil v roce 1926 jako prvni cesky matematik a profesor univerzity v Brne Otakar Boruvka. Reseni je velmi jednoduche, kostru vytvarime tak, ze zacneme od prazdne mnoziny a pridavame hranu po hrane, dokud nedostaneme kostru grafu. Hranu vzdy pridavame tak, aby nevytvorila kruznici, tj. abychom neustale meli acyklicky graf. Pokud hledame minimalni kostru, pak vzdy ze vsech hran vhodnych v danem kroku k pridani vybereme tu, ktera ma nejmensi vahu. Neustale tedy bereme to nejlepsi, co je po ruce - odtud se tento algoritmus nazyva hladovy (greedy).

      Profesor Boruvka ovsem nespecifikoval blize, jak se kontrola kruznic provadi. Ke kontrole kruznic se pouzivaji dva zname algoritmy - Kruskaluv a Primuv.

      Kruskaluv algoritmus si udrzuje mnozinu mnozin vrcholu, ktere jsou jiz spojeny nejakou cestou. Zacne mnozinou jednoprvkovych mnozin a pri pridani hrany odpovidajici dve mnoziny sjednoti do jedne. Hrana se totiz pridava tak, aby vychazela z jedne mnoziny a vchazela do jine. Pocet mnozin tedy vzdy o 1 klesne a na konci mame pouze jednu mnozinu obsahujici vsechny vrcholy.

      Primuv algoritmus vybira naslednou hranu vzdy tak, aby tvorila s jiz existujici mnozinou hran strom. Strom se rozrusta, az pokryje vsechny vrcholy. Hrana se vybira tak, aby mela minimalni vahu ze vsech vhodnych kandidatu.

Primuv algoritmus:

Vstup: graf G a pocatecni uzel s

seznam_inicializuj(S)
for each vrchol u do
  dist[u]:=Infinity
  pred[u]:=NIL
  seznam_uloz(S,u)
end for
dist[s]:=0;
while not seznam_prazdny(S) do
  u:=seznam_odeber_min(S)
  for each vrchol v sousedni s u do
    if seznam_obsahuje(S,v) and dist[v]>vaha[u,v] then
      dist[v]:=vaha[u,v]
      pred[v]:=u
    end if
  end for
end while

Vystup: pole dist obsahuje pro kazdy uzel u
                  vahu hrany vedouci do neho z pred[u]
        pole pred obsahuje pro kazdy uzel u
                  jeho bezprostredniho predchudce na ceste z s do u

Poznamka 1: Primuv algoritmus je velice podobny Dijkstrovu algoritmu. Rozdil je v tom, ze pole dist[u] ma jiny vyznam - neobsahuje delku cele cesty z s do u, nybrz pouze vahu jedne jedine hrany vedouci z predchudce uzlu u do u.

Poznamka 2: Vaha cele kostry se vypocte jednoduse jako soucet vsech dist[u] pres vsechny vrcholy u.