Topologické uspořádání
Topologické uspořádání uzlů grafu je taková posloupnost uzlů ui, uj, že pro každou hranu mezi těmito uzly platí, že i < j. Pokud si to představíme graficky, tak to znamená, že máme graf nakreslený takovým způsobem, že všechny orientované hrany směřují jedním směrem. Podmínkou z tohoto vycházející je acykličnost daného grafu.
Topologické uspořádání se používá často pro plánování na sobě závislých činností. Pokud tyto činnnosti vyková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 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.
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;
}
Závěr
Struktura: graf
Časová složitost algoritmu: O(|V| + |H|), kde |V| je počet vrholů grafu, |H| je počet hran grafu
Literatura
- KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.
