Skip to content

3.4 Topsort

Definice 3.5 (Topologické uspořádání)

Topologické uspořádání

Topologické uspořádání (TU) orientovaného grafu \(G = (V, E)\)

je takové seřazení vrcholů \(V = \{v_{1}, ... , v_{n}\}\), že pro každou orientovanou hranu \((v_{i}, v_{j} ) \in E\) platí \(i \lt j\).

  • Jinými slovy, pokud vrcholy zakreslíme horizontálně v pořadí topologického uspořádání, budou všechny orientované hrany směřovat zleva doprava.
  • Topologické uspořádání se používá především pro plánování pořadí provedení navzájem závislých úloh/výpočtů.

Cyklické závislosti

Získaný orientovaný graf však může obsahovat cyklus (orientovanou kružnici)

Pozorování

  • Pokud graf obsahuje cyklus, nelze tuto úlohu zjevně vyřešit.
  • Graf \(G\) může mít více topologických uspořádání

Definice 3.6 (Orientovaná kružnice)

Orientovaná kružnice

Nechť \(n \geq 1\). Orientovaná kružnice délky \(n\) (s \(n\) vrcholy) je orient. graf \((\{1, ... , n\}\), \(\{(i, i + 1) | i \in \{1, ... , n − 1\}\} \cup \{(n, 1)\})\).

Definice 3.7 (Acyklický graf)

Acyklický graf

Orientovaný graf \(G\) nazveme acyklický, pokud neobsahuje jako podgraf orientovanou kružnici.
angl. Directed Acyclic Graph (DAG)

Definice 3.8 (Zdroj a stok)

Zdroj a stok

  • Zdroj je takový vrchol orientovaného grafu, do kterého nevede žádná hrana.
  • Stok je takový vrchol orientovaného grafu, ze kterého nevede žádná hrana

Věta 3.5 (o existenci zdroje a stoku)

Věta o existenci zdroje a stoku

  • Nechť \(G = (V, E)\) je orientovaný acyklický graf. Potom \(G\) obsahuje aspoň jeden zdroj a aspoň jeden stok.
Důkaz Věty 3.5
  1. Sporem pro existenci zdroje (pro stok analogické).
  2. Předpokládejme, že v \(G\) neexistuje zdroj.
  3. Zvolme libovolný vrchol \(v_{1} \in V\) . Do něj, dle předchozího předpokladu, vede alespoň jedna orientovaná hrana z nějakého vrcholu \(v_{2}\).
  4. Do \(v_{2}\) také musí vést orientovaná hrana z nějakého vrcholu \(v_{3}\), a tak dále.
  5. Nejpozději po \(n\) krocích se však musí nějaký vrchol zopakovat.
  6. To ale znamená existenci cyklu v \(G\), čímž dostáváme SPOR.

Algoritmus 3.1 (Topsort)

Algoritmus Topsort

Existence zdroje v orientovaném acyklickém grafu vede přímočaře na algoritmus konstrukce topologického uspořádání takového grafu.

Vstup

Orientovaný graf \(G\).

Výstup

Nějaké topologické uspořádání \(G\), pokud byl acyklický
Detekce cykličnosti v opačném případě.

Idea

  • počítej vstupní stupně vrcholů (tj. počet hran, ve kterých je vrchol následníkem),
  • zdroje zařazuj do fronty,
  • odebírej vrcholy z fronty, zařazuj je do výstupního pořadí a odebírej je z grafu a to znamená, že jejich následníkům snižuj vstupní stupně.
  • Pokud po vyprázdnění fronty zbyly v grafu nějaké vrcholy, byl v něm orientovaný cyklus.

Algoritmus

Algoritmus TopSort(orientovaný G):
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Q je prázdná fronta
δ[] = pole vstupních stupňů vrcholů G, na počátku vynulované
Pro každou hranu (u, v) ∈ E(G):
    δ[v]++
Vlož do Q všechny vrcholy z s δ[z] = 0
Dokud fronta Q není prázdná:
    Odeber prvek z ze začátku fronty Q
    Vypiš z
    Pro každou hranu (z, w) vedoucí ze z:
        δ[w]−−
        Pokud δ[w] = 0: zařaď w do Q
Pokud nebyly zpracovány všechny vrcholy:
    graf G obsahuje orientovaný cyklus

Věta 3.6 (o správnosti algoritmu TopSort)

Věta o správnosti algoritmu TopSort

Algoritmus TopSort(\(G\)) spuštěný na orientovaný graf \(G\) doběhne v konečném čase a buď vygeneruje korektní topologické uspořádání acyklického grafu nebo detekuje existenci orientovaného cyklu.

Důkaz Věty 3.6
  1. Předpokládejme, že \(G\) je orientovaný graf a předpokládejme, že na počátku v kroku \((5)\) existuje aspoň jeden zdroj \(z\) a že všechny zdroje zařadíme do fronty \(Q\).
  2. Vnitřek cyklu \((7)-(11)\) realizuje odebrání \(1\) zdroje z fronty \(Q\), jeho vyjmutí z grafu \(G\), jeho vložení do výsledného uspořádání a identifikaci případných nových zdrojů a jejich zařazení do \(Q\).
  3. Existence hrany \((v_{i}, v_{j})\) znemožňuje vložit vrchol \(v_{j}\) do fronty \(Q\) před vrcholem \(v_{i}\), protože \(v_{j}\) by v takovém okamžiku mělo \(\delta [v_{j}] \geq 1\) a podmínkou vložení do \(Q\) je \(\delta [v_{j}] = 0\)
  4. Pokud v okamžiku vyprázdnění fronty jsou zpracovány všechny vrcholy grafu \(G\), našli jsme TU orientovaného acyklického grafu (RETURN).
  5. Pokud je fronta prázdná a přesto zbývají nějaké nezpracované vrcholy ve zbytku \(G\), pak ve zbytku \(G\) nejsou žádné zdroje, čili každý vrchol má vstupní hranu/-y a musí existovat orientovaný cyklus, plus případně z něj dostupné podgrafy. Vrcholy tohoto zbytkového grafu nelze topologicky uspořádat.
  6. Algoritmus tedy správně detekuje existenci cyklu a skončí v konečném čase.
  7. V obou případech algoritmus pracuje korektně a zastaví se.

Věta 3.7 (o složitosti algoritmu TopSort)

Věta o složitosti algoritmu TopSort

Algoritmus TopSort(\(G\)), kde \(G = (V, E)\) je orientovaný graf reprezentovaný pomocí pole následníků, má časovou i paměťovou složitost \(O(|V| + |E|)\).

Důkaz Věty 3.7
  1. Výpočet pole vstupních stupňů na řádcích \((3),(4)\) trvá \(\Theta (|E|)\).
  2. Počáteční vložení zdrojů do \(Q\) na řádku \((5)\) trvá \(O(|V|)\).
  3. Každý vrchol je vložen do \(Q\) nejvýše 1x, proto vybírání z \(Q\) a výpis na výstup na řádcích \((6)\)–\((8)\) trvá \(O(|V|)\).
  4. Každá hrana může být odebrána z grafu nejvýše 1x, proto operace na řádcích \((9)\)–\((11)\) trvají \(O(|E|)\).
  5. Celková časová složitost je tedy \(O(|V|+|E|)\).
  6. Graf \(G\), pole \(\delta\)[], fronta \(Q\), to vše zabere \(O(|V| + |E|)\) paměti.

K zamyšlení

  • Jak vypadají orientované grafy s právě dvěma topologickými uspořádáními?
  • Jak vypadají orientované grafy s právě třemi topologickými uspořádáními?
  • Fungoval by algoritmus TopSort i s jinou strukturou než frontou? Co třeba se zásobníkem?
  • Navrhněte, jak modifikovat algoritmus DFS pro orientované grafy, aby vytvořil TU grafu.
    • Nápověda 1: Vezmu-li orientovaný acyklický graf a nějaké jeho TU, jakou vlastnost musí mít poslední vrchol v TU?
    • Nápověda 2: Připusťme, že TU lze konstruovat odzadu.