TOPOLOGICKÉ TŘÍDĚNÍ
PROBLÉM
Budeme předpokládat, že objekty, které mají být utříděny, jsou očíslovány čísly of 1 do N. Vstupem algoritmu je graf bez cyklů, který může být reprezentován množinou číselných dvojic. Dvojice J K značí, že objekt J předchází objektu K v částečném uspořádání. Pak J je předchůdce K a K je následník J. Příkladem vstupu mohou být dvojice, pro N=9
9 2 3 7 7 5 5 8 8 6
4 6 1 3 7 4 9 5 2 8
|
Algoritmus musí objekty uspořádat do lineárního seznamu tak, aby předchůdci předcházely svým následovníkům. Řešením výše uvedeného zadání může být např.:
1 9 3 2 7 5 4 8 6
ALGORITMUS
Prvními na výstupu budou objekty bez předchůdců. Vyjmeme-li je z množiny vstupních objektů, bude výsledná množina opět částečně uspořádaná, a proces může pokračovat. Algoritmus si nejprve pro každý objekt poznamená počet jeho předchůdců a seznam následovníků. Výše uvedený graf s devíti uzly lze reprezentovat tabulkou:
| Reprezentace grafu |
| Objekt |
Počet předchůdců |
Seznam následovníků |
| 1 |
0 |
3 |
| 2 |
1 |
8 |
| 3 |
1 |
7 |
| 4 |
1 |
6 |
| 5 |
2 |
8 |
| 6 |
2 |
|
| 7 |
1 |
5 4 |
| 8 |
2 |
6 |
| 9 |
0 |
2 5 |
Algoritmus pak vybere objekty pro něž je Počet předchůdců roven 0, zapíše je na výstup a sníží počet předchůdců všech následovníků tohoto objektu o jedna. Pro zapamatování si pořadí, v jakém byly nalezeny objekty s nulovou hodnotou položky Počet předchůdců, využívá algoritmus datové struktury fronta.
IMPLEMENTACE
Jednotka: program
Vstupní data: Číslo N a posloupnost dvojic: předchůdce následovník.
Výsledek: Program vypisuje lineární posloupnost objektů, ve které každý předchůdce předchází svým následovníkům
/*
9 2 3 7 7 5 5 8 8 6
4 6 1 3 7 4 9 5 2 8
*/
Pocet. = 0; N = 9; Nasleduje. = ""
do I = 2 while SOURCELINE(I) <> "*/"
Veta = SOURCELINE(I)
do while Veta <> ""
parse var Veta J K Veta
Pocet.K = Pocet.K + 1
Nasleduje.J = Nasleduje.J K
end
end
do I = 1 to N; if Pocet.I = 0 then queue I; end
do while QUEUED() <> 0
pull K; say K; N = N - 1
Nasledovnici = Nasleduje.K
do while Nasledovnici <> ""
parse var Nasledovnici S Nasledovnici
Pocet.S = Pocet.S - 1
if Pocet.S = 0 then queue S
end
end
if N <> 0 then
say "TOPOLOGICAL_SORT: Chyba",
"- cyklus v grafu"
|
Literatura
Bentley J. More Programming Pearls - Confession of a Coder
Addison-Wesley, 1990
Knuth D. E. Fundamental Algorithms, vol. 1 of The Art of Computer Programming, second edition
Addison-Wesley, 1973
