Skip to main content.

Zaradenie a popis

Prehľadávanie do hĺbky (Depth-first search - DFS) je algoritmus, pomocou ktorého je možné efektívne preskúmať každý vrchol a každú hranu grafu systematickým spôsobom. Algoritmus začne vo vrchole a preskúmava graf čo najďalej (najhlbšie) a až potom pokračuje v backtrackingu.

DFS sa používa napríklad pri riešní nasledujúcich problémov:
 a) Nájdenie komponentov v grafe.
 b) Topologické triedenie.
 c) Hľadanie silne súvislých komponentov.

^ TOP

Myšlienka algoritmu

Prehľadávanie do hĺbky je neinformované prehľadávanie, ktoré pracuje nasledovným spôsobom: algoritmus začne v počiatočnom vrchole a rekurzívne sa zavolá na prvom susednom vrchole. Pamätá si, ktorými vrcholmi už prechádzal a do tých vrcholov nevstupuje. Takto pokračuje, až kým nenarazí na cieľový vrchol alebo už nemá kam pokračovať (tj. vrchol nemá žiadnych susedov, ktorých algoritmus ešte nenavšívil).
Ak graf obsahuje viac komponentov, skontroluje sa či boli navštívené všetky vrcholy a ak nie, vyberie sa jeden z nich a spustí sa z neho prehľadávanie (takto vieme zistiť počet a konfiguráciu komponentov v grafe).
V nerekurzívnej verzii sa všetky nové prehľadávané vrcholy ukladajú do zásobníka.

^ TOP

Vizualizácia

^ TOP

Zápis algoritmu

    int graph[N][N];
    int color[N];
    
    /*prehladaj z vrcholu v */
    void visit(int v)
    {
      int i;
      /* zaciatok */
      color[v]=GRAY;
      for(i=0;i<n;i++)
        if(graph[v][i]!=0)
         if (color[i]==WHITE)
           visit(i);
      /* koniec */
     color[v]=BLACK;
    }
    
    /* prehladavanie do hlbky */
    void dfs(void)
    {
      int i;
      /* kazdy vrchol zafarbime na bielo */
      for(i=0;i<n;i++)
        color[i]=WHITE;
      /* zacni z neofarbeneho vrcholu */
      for(i=0;i<n;i++)
        if (color[i]==WHITE)
          visit(i);
    }
^ TOP

Vlastnosti algoritmu

Keďže prehľadávanie do hĺbky prespektívne skontroluje každý vrchol a každú hranu v grafe, jeho časová zložitosť je O(|V| + |E|), kde V je množina vrcholov a E množina hrán. Pamäťová zložitosť je oveľa nižšia ako pri prehľadávaní do šírky.

^ TOP

Experimentovanie

Dipl.-Inform. Thomas Wolf
Prostredie na experimentovanie s grafmi.
http://www.lupinho.de/gishur/html/DFSApplet.html

^ TOP