Topologické uspořádání je taková posloupnost uzlů grafu, že pro každou jeho hranu platí, že uzel je zařazen před uzlem . 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 , kde je počet uzlů grafu a 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.