Popis algoritmu hledání minimální kostry orientovaného grafu

Právě se mi podařilo získat 6/10, tak snad už mám řešení a pochopení natolik dobré, abych se zde mohl podělit.

V dalším textu bude detailně popisován algoritmus sepsaný Ali Tofighem v Optimum Branchings and Spanning Aborescences (odkaz je na stránce úkolu - algorithm-description.pdf). Pokusím se popsat i optimální implementaci datových struktur.

V algoritmu potřebujeme union-find množiny, které budou reprezentovat slabé a silné komponenty grafu a umožní nám snadno provádět jejich slučování. Strukturu je možné navrhnout například jako pole, kde index prvku odpovídá číslu vrcholu/komponenty a hodnota prvku odpovídá reprezentantu množiny. Funkce find pak vrací reprezentanta množiny, union slučuje dvě množiny. Je potřeba, aby find snižoval výšku stromu množiny. Snad jasné.

Každý vrchol grafu si musí pamatovat množinu hran, které do něj vstupují. Z těchto hran bude vybírána vždy ta nejmenší. Dále bude potřeba umět dvě takovéto množiny efektivně sloučit (log n) a v konstantním! čase zvýšit váhu všech hran. Tohoto nejlépe docílíme právě upravenou binomickou haldou.

Nejtěžší je pravděpodobně zvyšování váhy všech vah. To lze provést tak, že přírůstek vah uložíme v prvním kroku jen do pomocné struktury haldy a dále tuto hodnotu šíříme haldou až v případě potřeby (odebírání vrcholu, slučování dvou hald). Každý uzel haldy si bude pamatovat kromě své váhy/klíče i přírůstek. Přitom je vhodné, aby platilo, že celková váha nějakého uzlu je součet vah jeho rodičů (včetně té pomocné struktury haldy), jeho přírůstku a jeho vlastní váhy.

Propagace do nižších pater haldy probíhá vždy, když by se narušily správné celkové hodnoty vah uzlů. Jedním příkladem je odebírání minima z haldy. Pokud uzel minima obsahuje přírůstek, jeho pouhým odebráním bychom o něj přišli. Musíme tedy tento přírůstek propagovat do jeho potomků (o jedno patro níž). Další příklad je sloučení dvou hald. V takovém případě nemůžeme ponechat přírůstek v pomocné proměnné…atd. Doporučuju dobře otestovat, je to celkem fuška.