Prohledávání do hloubky

Otevírání a uzavírání uzlů při procházení grafu do hloubky

Prohledávání do hloubky (depth-first search, DFS) je algoritmus určený k procházení grafu, který má široké uplatnění - jeho principů se využívá při zjišťování počtu komponent, topologického uspořádání nebo detekci cyklů daného grafu.

Princip

Algoritmus zvolí libovolný uzel a označí jej jako otevřený, zpracuje jej a zavolá sám sebe na všechny dosud neobjevené potomky daného uzlu. Po návratu z rekurze uzel označí jako uzavřený. Tímto způsobem dojde k průchodu všech větví grafu do maximální hloubky.

Složitost

Za předpokladu, že lze přistoupit k sousedům daného uzlu v konstantním čase, tak je asymptotická složitost tohoto algoritmu $O(\\vert U \\vert + \\vert H \\vert)$ , protože projde každým uzlem i hranou právě jednou.

Kód

Java

 
     /**
      * Dosud neobjeveny uzel
      */
     private static final int FRESH = 0;
     /**
      * Otevreny uzel
      */
     private static final int OPEN = 1;
     /**
      * Uzavreny uzel
      */
     private static final int CLOSED = 2;
 
     /**
      * Prohledavani do hloubky (rekurzivne)
      *
      * @param graph
      */
     public static void depthFirstSearch(GraphIface graph) {
         //Stavy jednotlivych uzlu
         int[] state = new int[graph.getVertexCount()];
 
         for (int i = 0; i < state.length; i++) {
             state[i] = FRESH;
         }
         //zajisti pruchod vsemi komponentami souvislosti
         for (int i = 0; i < graph.getVertexCount(); i++) {
             if (state[i] == FRESH) {
                 doDFS(graph, i, state);
             }
         }
     }
 
     /**
      * Provede prohledavani do hloubky
      *
      * @param graph graf
      * @param vertexNr cislo uzlu
      * @param state stavy uzlu
      */
     private static void doDFS(GraphIface graph, int vertexNr, int[] state) {
         state[vertexNr] = OPEN;
         List<GraphNodeIface> succ = graph.getNode(vertexNr).getSuccessors();
         for (GraphNodeIface n : succ) {
             if (state[n.getId()] == FRESH) {
                 doDFS(graph, n.getId(), state);
             }
         }
         state[vertexNr] = CLOSED;
     }
 
     /**
      * Operace, ktere by mel splnovat graf
      *
      * @author Pavel Micka
      */
     public interface GraphIface<ENTITY> {
 
         /**
          * Prida hranu do grafu
          *
          * @param from uzel, ze ktereho hrana vychazi
          * @param to uzel, do ktereho hrana vede
          */
         public void addEdge(int from, int to);
 
         /**
          * Vrati pocet hran grafu
          *
          * @return pocet hran grafu
          */
         public int getEdgeCount();
 
         /**
          * Vrati uzel s danym identifikatorem
          *
          * @param id
          * @return
          */
         public GraphNodeIface getNode(int id);
 
         /**
          * Vrati pocet vrcholu grafu
          *
          * @return pocet vrcholu grafu
          */
         public int getVertexCount();
 
         /**
          * Odstrani hranu, v pripade vicenasobneho vyskytu odstrani prvni vyskyt
          *
          * @param from uzel, ze ktereho hrana vychazi
          * @param to uzel, do ktereho hrana vede
          */
         public void removeEdge(int from, int to);
 
         /**
          * Operace, ktere by mel splnovat uzel grafu
          *
          * @param <ENTITY>
          */
         public interface GraphNodeIface<ENTITY> {
 
             /**
              * @return the id
              */
             public int getId();
 
             /**
              * @return the successors
              */
             public List<GraphNodeIface> getSuccessors();
 
             /**
              * @return the value
              */
             public ENTITY getValue();
 
             /**
              * @param value the value to set
              */
             public void setValue(ENTITY value);
         }
     }

Literatura

KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.

Princip

Složitost

Kód

Literatura

Doporučujeme