Відкрити головне меню

Топологічне сортування — впорядковування вершин безконтурного орієнтованого графа згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин.

ПрикладРедагувати

Для графу  

 
Безконтурний орієнтований граф

існує декілька узгоджених послідовностей його вершин, які можуть бути отримані за допомогою топологічного сортування, наприклад:

  •  
  •  
  •  

Видно, що в послідовності можуть брати участь будь-які дві вершини, що не входять у відношення часткового порядку  .

АлгоритмиРедагувати

Час виконання для звичайного алгоритму топологічного сортування лінійний до кількості вершин плюс кількість ребер  

Один з цих алгоритмів працює, вибираючи вершини в тому самому порядку, що і випадкове топологічне сортування. Спочатку знаходить набір «початкових вершин», які не мають ребер, що входять, і вставляє їх в набір S; щонайменше одна така вершина має існувати, якщо граф ациклічний. Тоді:

L ← Порожній список, що буде містити відсортовані елементи
S ← Набір вершин без ребер, що входять
доки S не порожнє виконати
    видалити вершину n з S
    вставити n в L
    для кожної вершини m з ребром e з n до m виконувати
        видалити ребро e з графа
        якщо m не має більше ребер, що входять тоді
            вставити m в S
якщо граф має ребра тоді
    вивести повідомлення про помилку (у графа є як мінімум один цикл)
інакше 
    вивести повідомлення (пропоноване топологічне сортування: L)

Якщо маємо справу з орієнтованим ациклічним графом, то алгоритм видасть рішення (не унікальне).

Альтернативний алгоритм базується на пошуку в глибину. Для цього алгоритму ребра вказуються у зворотному напрямку. Тобто якщо ребро іде з x до y, то це означає, що робота x залежить від роботи y (іншими словами робота y має бути завершена перед тим, як x зможе стартувати). Алгоритм проходить кожну вершину в графі в довільному порядку, започатковуючи пошук у глибину, що закінчується коли досягає вершину, яку вже відвідали з початку сортування:

L ← Порожній список, що буде містити відсортований набір вершин
S ← Набір всіх вершин
функція відвідати(вершина n)
    якщо n ще не була відвідана тоді
        помітити n як відвідану
        для кожної вершини m з ребром від n до m виконати
            відвідати(m)
        додати n до L
для кожної вершини n в S виконати
    відвідати(n)

ЗастосуванняРедагувати

За допомогою топологічного сортування будується коректна послідовність виконання дій, будь-яка з яких може залежати від іншої: послідовність проходження навчальних курсів студентами, збірки вихідних текстів програм за допомогою Makefile'ів.

ПосиланняРедагувати