Тополошко сортирање

Из Википедије, слободне енциклопедије

У теорији графова, тополошко сортирање усмереног ацикличног графа је линеарно уређење његових чворова, које је компатибилно са парцијалним уређењем R индукованим на чворовима где x долази пре y (xRy) ако постоји усмерен пут од x у y усмереном ацикличном графу. Еквивалентна дефиниција је да сваки чвор долази пре свих чворова до којих из њега постоји пут. Сваки усмерени ациклични граф има једно или више тополошких сортирања.

Примери[уреди]

Канонска примена тополошког сортирања је у прављењу распореда неких послова. Послови су представљени чворовима, и постоји грана од x до y ако посао x мора бити завршен пре него што се може прећи на посао y (на пример, машина за прање веша мора да заврши са прањем да би се веш простро на сушење). Тада тополошко сортирање даје редослед по којима се послови могу извршавати. Ово има разне примене у рачунарству. Осим тога, тополошко сортирање се може користити за једноставно проналажење најкраћих путева до свих чворова од неког чвора усмереног ацикличног графа.

Directed acyclic graph.png
Овај граф има многа исправна тополошка сортирања, међу којима су:
  • 7,5,3,11,8,2,10,9
  • 7,5,11,2,3,10,8,9
  • 3,7,8,5,11,10,9,2

Алгоритми[уреди]

Уобичајени алгоритми за тополошко сортирање имају линеарну сложеност по броју чворова плус броју грана V|+|E|)).

Један од ових алгоритама ради на следећи начин. Прво се сачини списак чворова у које ниједна грана не улази (најмање један такав чвор (са улазним степеном нула) мора да постоји ако је граф ацикличан), и оне се сместе у ред Q. Затим,

Q ← скуп свих чворова без улазних грана
док Q није празно уради
    уклони чвор n из Q
    испиши n
    за сваки чвор m са граном e из n у m уради
        уклони грану e из графа
        ако m нема других улазних грана онда
            убаци m у Q
ако граф има грана онда
    испиши поруку о грешци (граф има цикл)

Ако овај алгоритам заврши пре него што испише све чворове графа, то значи да граф има најмање један цикл, и да није усмерени ациклични граф, па је тополошко сортирање немогуће. Због чињенице да сортирање није јединствено, структура Q не мора да буде ред; може се користити и стек, или просто скуп.

Спољашње везе[уреди]

Литература[уреди]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press and McGraw-Hill.