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řadí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání
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 úplně jedno, v jakém vrcholu začneme graf prohledávat, protože díky ukládání do zásobníku se ve výsledku vždyy seřadí tak, jak potřebujeme. (př: když začneme od kalhot, tak se na dno zásobníku uloží boty a nad ně kalhoty. Tady jsme skončili, takže pokračujeme v prohledávání od jiného nenavštíveného uzlu - třeba od spodků. Ty se tedy uloží nad boty a kalhoty, takže když vybíráme ze zásobníku, dostaneme správně spodky->kalhoty->boty. Pokud bychom místo spodků pokračovali třeba ponožkami, nic se nestane, jen bude do této podloupnoosti vložen ještě prvek ponožky: spodky->ponožky->kalhoty->boty, ale posloupnost bude stále zachována taková, aby položky následovaly tak jak mají.)
