Prohledávání do šířky

Při prohledávání do šířky začneme procházet graf z libovolně zvoleného vrcholu s. Provádí systematicky expanzi listů, po patrech (sousedech).

Zaručuje nám, že výsledná cesta z s do jiného vrcholu bude mít nejmenší možný počet hran. Je vhodný pro řešení uloh typu: nalezení nejkratší cesty z vybraného vrcholu, hledání souvislé komponenty1 či koster souvislých grafů.

Princip

Každý vrchol se může nacházet v jednom z následujících stavů: {FRESH, OPEN, CLOSE}. Potřebujeme odlišit navštívené a nenavštívené vrcholy. Na počátku označíme všechny stavy jako FRESH (nenavštívený).

Algoritmus využívá datovou strukturu fronty do které přidává vrcholy a provádí nad ní iterace.

Začneme procházet graf z s, tento vrchol nejprve vložíme do prázdné fronty Q. Následně vrchol navštívíme, vrchol odebereme z fronty Q a jeho nenavštívené sousední vrcholy vložíme do fronty. Abychom věděli, který vrchol navštívit dál, vezmeme vrchol ze začátku fronty Q a zopakujeme předchozí kroky, dokud fronta není prázdná.

Pseudokód

Algoritmus BFS(G, s):
pro každý vrchol v ∈ V(G):
    stav(v) := nenavštívený
    D(v) := P(v) := undef
stav(s) := navštívený
D(s) := 0
Q := fronta obsahující s
Dokud je fronta Q neprázdná:
        Odeber začátek fronty Q, označ ho v
    Pro všechny sousedy w vrcholu v:
        Pokud stav(w) = nenavštívený:
            stav(w) := otevřený
            D(w) := D(v) + 1
            P(w) := v
            přidej w do fronty Q
    stav(v) := uzavřený

Časová složitost

Při reprezentaci grafu seznamem sousedů má časovou složitost O(|V|+|E|).

Důkaz

  1. Každý vrchol je přidán do fronty Q nejvýše jednou, neboť je předtím otevřen a nemůže už tedy vícekrát splnit podmínku na řádku(10).
  2. V každé iteraci cyklu (7)–(15) je jeden vrchol odebrán z fronty, tento cyklus má tedy nejvýše |V| iterací.
  3. Celkový počet iterací cyklu (9)–(14) je nejvýše dvakrát tolik, kolik je v grafu hran (jednou „pohled“ hranou z jedné strany, podruhé z opačné).
  4. Celková časová složitost je tedy O(|V|+|E|)

Paměťová složitost

Algoritmus BFS má při reprezentaci grafu seznamem sousedů paměťovou složitost O(|V|+|E|).

Důkaz

  1. Reprezentace seznamem sousedů zabírá O(|V|+|E|) paměti.
  2. Pomocná pole zabírají nejvýše O(|V|)paměti.
  3. Ve frontě je každý prvek nejvýše jednou, má tedy délku nejvýše|V|, čili zabere maximálně O(|V|)paměti.
  4. Celkem tedy O(|V|+|E|).

  1. komponenta souvislosti ↩

Související