Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Topologické třídění

Definice

Topologické uspořádání vrcholů orientovaného grafu je funkce taková, že pro každou hranu je . Lze provést pouze pro acyklické orientované grafy.

Algoritmus (Primitivní algoritmus)

V každém kroku najde vrchol, z něhož nevedou žádné hrany. Přiřadí mu nejvyšší volné číslo (začíná od ) a odstraní ho ze seznamu vrcholů. Uspořádání takto vytvořené je topologické, složitost algoritmu je .

Algoritmus (Rychlý algoritmus)

K topologickému uspořádání se dá použít modifikace prohledávání do hloubky. Není třeba ani graf předem testovat na přítomnost cyklů, algoritmus toto objeví. Pro každý navštívený vrchol si poznamená čas jeho opuštění, uspořádání podle klesajících časů opuštění je topologické.

    topologické_třídění( v - vrchol ) {

    global t; // čas opuštění, iniciální hodnota 0

    označ v jako navštívený;
    foreach ( u in sousední vrcholy v ) {
    if ( u je navštívený, ale ne opuštěný ) {
    chyba - cyklus;
    return;
    }
    else if ( u není navštívený )
    topologické_třídění( u );
    }
    označ v jako opuštěný v čase t;
    t = t + 1;
    }

Časová složitost zůstává stejná jako u prohledávání do šířky, tedy , protože všechny kroky prováděné v rámci navštívení 1 vrcholu vyžadují jen konstatní počet operací.

Poznámka

Topologické třídění se používá např. k zjištění nejvhodnějšího pořadí provedení navzájem závislých činností.