Autor : Milan Parys , L95416

Nejlevnější kostra

Jarníkův algoritmus

Je to modifkace základního algoritmu, tentokrát nazvaná podle známeho českého matematika profesora Vojtěcha Jarníka (1930). Začneme z libovolného vrcholu a postupně k němu přidáváme vrcholy a hrany tak, že v každé fázi výpočtu máme strom. Přidávanou hranu přitom vždy vybíráme tak, aby měla nejmenší cenu z množiny Wg (A) (všechny hrany, které mají jeden krajní vrchol v množině A a druhý v V(G)-A), kde A je množina vrcholů stromu.

Nalezení nejlevnější kostry pomocí tohoto algoritmu je určenou pouze pro neorientované grafy, proto zanedbáme orientaci anšich hran.

Použijeme zde pole m[99] jako indikátor příslušnosti uzlu k množině A (pokud je m[i]=1 pak u[i] patří do A). Dále setřídíme vzestupně pole všech hran pomocí algoritmu QuickSort (funkce qsort). Pak vezmeme uzel 1 jako výchozí a vložíme ho do množiny A.
Postupně procházíme pole hran od začátku (od nejlevnější) a hledáme hranu s jedním vrcholem ve stromu a druhým mimo něj.
Pokud takovou hranu najdeme, označíme ji, přičteme její cenu k ceně kostry, přidáme její koncové uzly do množiny A a zvíšíme počítadlo uzlů a hran patřících do stromu.
Pokud takovou hranu nenajdeme a ve stromu ještě nejsou všechny uzly grafu pak je graf nesouvislý a nemůžeme najít nejlevnější kostru.

Algoritmus vykreslí nejlevnější kostru jinou barvou a spočte jejícenu.