11.3 Implementace Jarníkova algoritmu

• V Jarníkově algoritmu opakovaně vybíráme nejlehčí hranu a odstraňujeme ji ze seznamu.
• Z Přednášky 4 víme, že efektivní odebírání minim z dynamicky se měnící množiny dokáže binární halda.

• Ukažme si nyní tedy implementaci pomocí binární haldy.

• Vrcholy grafu \(G\) jsou udržovány v binární haldě \(H\) uspořádané podle hodnoty klíčů \(d\), určujících „vzdálenost“ vrcholů od dosud vybudovaného stromu v daném kroku algoritmu.

• Na počátku je \(d(v)\) nekonečno pro všechny vrcholy a zvolený \(v_0\) má nulu.
• Z haldy vybereme pomocí ExtractMin vrchol \(u\) s minimálním \(d\), čímž ho přidáme ke stromu a přepočteme pro jeho sousedy \(v\) vzdálenosti \(d\).
• Pokud se jejich \(d\) změnilo, pomocí DecreaseKey aktualizujeme haldu a vrchol \(u\) se stává jejich předchůdcem.
• Minimum aktualizované haldy je rovno váze nejlehčí hrany v elementárním řezu mezi novým \(T\) a zbytkem grafu.

Věta 11.5 (o časové složitosti Jarníkova algoritmu s binární haldou)

Časová složitost MinKostraJarník při použití binární haldy je \(O(|E|\ \log|V|)\).

Důkaz věty 11.5

• Inicializace zabere \(O(|V|)\).
• Operace s binární haldou:
  • Provedeme \(|V| − 1\) krát operaci HeapExtractMin – celkem \(O(|V|\ \log|V|)\).
  • Každá hrana může způsobit volání operace HeapDecreaseKey – celkem \(O(|E|\ \log |V|)\).

Dohromady dostáváme \(O(|V|) + O(|V|\ \log|V|) + O(|E|\ \log|V|) = O(|E|\ \log|V|)\).