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


Obálka Obsah Index Hlavní stránka

změněno 1. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.