Topologické uspořádání
Topologicky uspořádaný graf
Topologicky uspořádaný graf

Topologické uspořádání je taková posloupnost uzlů grafu, že pro každou jeho hranu (u, \\; v) platí, že uzel u je zařazen před uzlem v. Topologicky lze proto uspořádat pouze acyklické grafy.

Pokud topologicky uspořádaný graf zakreslíme, tak všechny jeho hrany vedou právě jedním směrem.

Využití

Topologické uspořádání se například používá pro plánování vzájemně závislých činností. Pokud tyto činnosti vykonáváme v pořadí daném topologickým uspořádáním, tak daná činnost bude vždy vykonána až po všech činnostech, na kterých závisí.

Algoritmus

Algoritmus topologického uspořádání vychází z procházení grafu do hloubky. Jedná se o pořadí uzavření uzlů opačně orientovaného grafu. Časová složitost tohoto postupu proto O(\\vert U \\vert + \\vert H \\vert), kde \\vert U \\vert je počet uzlů grafu a \\vert H \\vert je počet jeho hran.


Kód

     /**
      * Vypise topologicke usporadani acyklickeho grafu
      * @param graph graf
      */
     public static void orderTopologically(GraphIface graph){
         //Stavy jednotlivych uzlu
         List<Integer> roots = new ArrayList<Integer>();
         for(int i = 0; i < graph.getVertexCount(); i++){
             //pokud nema v puvodnim grafu potomky, tak je korenem 
             //v opacne orientovanem grafu
             if(graph.getEdges(i).size() == 0) roots.add(i);
         }
         GraphIface inverted = graph.inverse(); //vytvor opacne orientovany graf
         int[] state = new int[inverted.getVertexCount()];
 
         for(int i = 0; i < state.length; i++) state[i] = FRESH;
         for(Integer i : roots){
             doOrdering(inverted, i, state);
         }
     }
     /**
      * Provadi samotne usporadani grafu
      * @param graph graf
      * @param vertexNr cislo aktualniho uzlu
      * @param state pole stavu
      */
     private static void doOrdering(GraphIface graph, int vertexNr, int[] state) {
         state[vertexNr] = OPENED;
         for(Integer i : graph.getEdges(vertexNr)){
             if(state[i] == FRESH) doOrdering(graph, i, state);
             else if(state[i] == OPENED) throw new IllegalArgumentException("Graf obsahuje cykly");
         }
         System.out.print(" -> " + vertexNr);
         state[vertexNr] = CLOSED;
     }
 

Literatura

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







Doporučujeme