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.

SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz

Hrajte nejlepší hry jako je GoodGame Empire.





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 VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor


Doporučujeme

Internet pro vaši firmu na míru

https://www.algoritmy.net