Топологічне сортування

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

Приклад

Для графу

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

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

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

Алгоритми

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

Один з цих алгоритмів (Кан, 1962[1]) працює, вибираючи вершини в тому самому порядку, що і випадкове топологічне сортування. Спочатку знаходить набір «початкових вершин», які не мають ребер, що входять, і вставляє їх в набір 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'ів.

Примітки

  1. Kahn, Arthur B. (1962). Topological sorting of large networks. Communications of the ACM 5 (11): 558–562. doi:10.1145/368996.369025.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.