Topologické řazení

Máme množinu prvků, ve které je definována množina dvojic, které jsou uspořádánvy v určitém pořadí. Tuto množinu lze zakreslit jako orientovaný graf, kdy každá hrana reprezentuje pořadí prvků.

Jako příklad může posloužit proces oblékání.

Dvojice jsou (musíme obléci): Ponožky dříve než boty Spodky dříve než kalhoty Kalhoty dříve než boty Košili dříve než sako a hodinky nezávisle na zbytku

V grafu vidíme, že obsahuje 3 komponenty, a že neobsahuje cykly. Pokud orientovaný graf neobsahuje cykly, nazývá se orientovaný acyklický graf (anglicky DAG, directed acyclyc graph). V takovém grafu lze nalézt uspořádání takové, že prvky budou chronologicky za sebou podle toho, v jakém pořadí je třeba je projít (vykonat jejich akce, obléci daný kus oblečení), např. takto

Jedním z algoritmů je Topologické řazení pomocí DSF:

Projdeme graf pomocí DFS, a při každé operaci (každém obarvení: nalezení/přesun na vrchol (šedá) a dokončení vyhledávání okolních vrcholů (černá)) pamatujeme čas, ve kterém jsme operaci provedli. První číslo udává "čas" nalezení vrcholu, druhé "čas" zpracování vrcholu. Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání

Topologicke-razeni-2.jpg

Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.