Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Prohledávání do hloubky a do šířky

Algoritmy, které postupně projdou všechny vrcholy daného souvislého neorientovaného grafu.

Algoritmus (Prohledávání do šířky/Breadth-First Search)

Prochází všechny vrcholy grafu postupně po vrstvách vzdáleností od iniciálního vrcholu. K implementaci se používá fronta (FIFO).

    BFS( V - vrcholy, E - hrany, s - startovací vrchol ){
    obarvi vrcholy bíle, nastav jim nekonečnou vzdálenost od s a předchůdce NULL;
    dej do fronty vrchol s;

    while( neprázdná fronta ){
    vyber z fronty vrchol v;
    foreach( všechny bíle obarvené sousedy v = u ){
    obarvi u šedě a nastav mu vzdálenost d(v) + 1 a předchůdce v;
    dej vrchol u do fronty;
    }
    v přebarvi na černo a vyhoď z fronty.
    }
    }

Běží v čase , protože každý vrchol testuje 2x pro každou hranu, do fronty ho dává 1x a obarvení mu mění 2x. Tento algoritmus je základem několika dalších, např. pro testování souvislosti grafu, hledání minimální kostry nebo nejkratší cesty.

Algoritmus (Prohledávání do hloubky/Depth-First Search)

Prochází postupně všechny vrcholy - do hloubky (pro každý vrchol nejdřív navštíví první jeho nenavštívený sousední vrchol, pak první sousední tohoto vrcholu atp. až dojde k vrcholu bez nenavštívených sousedů, pak se vrací a prochází další ještě nenavštívené sousedy). Pro implementaci se používá buď zásobník, nebo rekurze. Zásobníková verze vypadá stejně jako prohledávání do šířky (místo fronty je zásobník).

Rekurzivní verze - při zavolání na startovní vrchol projde celý graf:

    DFS(v - vrchol){

    označ v jako navštívený;
    foreach( všechny nenavštívené sousedy v = u )
    DFS( u );
    }

Časová složitost je , stejně jako u prohledávání do šířky.