Algoritmus BFS

Fáze

  • Značíme
  • Fáze trvá od odebrání vrcholu z fronty , otevření a vložení všech jeho sousedů do až do uzavření vrcholu
  • Fáze trvá od konce fáze až po uzavření všech vrcholů z
  • - číslo poslední fáze

Hladina

  • Značíme
  • je množina všech vrcholů otevřených a vložených do fronty ve fázi

Příklad hladin v grafu:
../Attachments/01-hladiny.png

Analýza složitosti BFS

(Souvisí s 02 Výpočetní model RAM)

Časová složitost

Odůvodnění:

  • Každý vrchol do BFS přidáme nejvýše jednou
  • V každé iteraci je 1 vrchol odebrán z fronty, má tedy nejvýše iterací
  • Asymptoticky - lineární
    • = počet vrcholů
    • = počet hran

Paměťová složitost

  • Lepší je seznam sousedů oproti 2D matici
  • Pole stav, pole sousedů, fronta
  • Asymptoticky - lineární

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