Minimální kostra grafu

  • Kostra: Podgraf, který obsahuje všechny vrcholy a je to strom, má tedy hran
    ../Attachments/Pasted image 20221128092350.png

Jarníkův algoritmus

  • (také Primův algoritmus v angličtině)

  • Nejjednodušší

  • Postup:

    • Začneme se stromem, který obsahuje libovolný jeden vrchol a žádné hrany (vyberu náhodný vrchol)
    • Vybereme nejlehčí hranu incidentní s tímto vrcholem (tedy nějakou z řezu mezi aktuálním stromem a zbytkem grafu)
    • Přidáme ji do stromu i s novým koncovým vrcholem (tedy už mám 2 vrcholy)
    • Postup opakujeme: v každém dalším kroku přidáváme nejlehčí z hran, které vedou mezi vrcholy dosud vytvořeného stromu a zbytkem grafu
    • Takto pokračujeme, dokud nevznikne celá kostra

  • Tzv. hladový algoritmus

  • Pokud jsou váhy unikátní, je minimální kostra jen jedna jediná

  • Časová složitost:

    • Protože krát hledáme nejlehčí hranu v seznamu nejvýše hran

  • Paměťová složitost:

Důsledek
  • Minimální kostra je jednoznačně určena uspořádáním hran podle vah, na konkrétních hodnotách vah nezáleží.
  • Tj. potřebujeme umět hrany porovnávat, ne znát jejich konkrétní hodnoty.
  • Jarníkův algoritmus váhy hran mezi sebou pouze porovnává. Řešitelné v nějakém porovnávavím modelu.

Kruskalův algoritmus

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25