Topologické uspořádání

Topologicky uspořádaný graf

Topologické uspořádání je taková posloupnost uzlů grafu, že pro každou jeho hranu $(u, \\; v)$ 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 $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

Java

/**
 * 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.

Využití

Algoritmus

Kód

Literatura

Doporučujeme