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.

www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino