Topologické řazení
| Řádka 6: | Řádka 6: | ||
Dvojice jsou (musíme obléci): | Dvojice jsou (musíme obléci): | ||
| − | Ponožky dříve než boty | + | * Ponožky dříve než boty |
| − | Spodky dříve než kalhoty | + | * Spodky dříve než kalhoty |
| − | Kalhoty dříve než boty | + | * Kalhoty dříve než boty |
| − | Košili dříve než sako | + | * Košili dříve než sako |
| − | a hodinky nezávisle na zbytku | + | * 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 | 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 | ||
| Řádka 19: | Řádka 19: | ||
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. | 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 | 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 | + | 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í |
[[Soubor:Topologicke-razeni-2.jpg]] | [[Soubor: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ý. | 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ý. | ||
Verze z 26. 8. 2011, 08:36
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 evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.
