Топологічне сортування — впорядковування вершин безконтурного орієнтованого графу згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин.
Приклад
Для графу
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekE0TDBScGNtVmpkR1ZrWDJGamVXTnNhV05mWjNKaGNHZ3VjRzVuTHpJeU1IQjRMVVJwY21WamRHVmtYMkZqZVdOc2FXTmZaM0poY0dndWNHNW4ucG5n.png)
існує декілька узгоджених послідовностей його вершин, які можуть бути отримані за допомогою топологічного сортування, наприклад:
Видно, що в послідовності можуть брати участь будь-які дві вершини, що не входять у відношення часткового порядку .
Алгоритми
Час виконання для звичайного алгоритму топологічного сортування лінійний до кількості вершин плюс кількість ребер
Один з цих алгоритмів (Кан, 1962) працює, вибираючи вершини в тому самому порядку, що і випадкове топологічне сортування. Спочатку знаходить набір «початкових вершин», які не мають ребер, що входять, і вставляє їх в набір 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'ів.
Примітки
- Kahn, Arthur B. (1962), Topological sorting of large networks, Communications of the ACM, 5 (11): 558—562, doi:10.1145/368996.369025
Посилання
- NIST Dictionary of Algorithms and Data Structures: topological sort
- Weisstein, Eric W. TopologicalSort(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Topologichne sortuvannya vporyadkovuvannya vershin bezkonturnogo oriyentovanogo grafu zgidno z chastkovim poryadkom viznachenim rebrami cogo grafu na mnozhini jogo vershin PrikladDlya grafu G 2 3 5 7 8 9 10 11 3 8 3 10 5 11 7 11 7 8 8 9 11 2 11 9 11 10 displaystyle G bigl 2 3 5 7 8 9 10 11 bigr bigl 3 8 3 10 5 11 7 11 7 8 8 9 11 2 11 9 11 10 bigr Bigr Bezkonturnij oriyentovanij graf isnuye dekilka uzgodzhenih poslidovnostej jogo vershin yaki mozhut buti otrimani za dopomogoyu topologichnogo sortuvannya napriklad 7 5 11 3 8 2 9 10 displaystyle 7 5 11 3 8 2 9 10 3 7 5 8 11 10 9 2 displaystyle 3 7 5 8 11 10 9 2 7 5 11 2 3 8 9 10 displaystyle 7 5 11 2 3 8 9 10 Vidno sho v poslidovnosti mozhut brati uchast bud yaki dvi vershini sho ne vhodyat u vidnoshennya chastkovogo poryadku E displaystyle E AlgoritmiChas vikonannya dlya zvichajnogo algoritmu topologichnogo sortuvannya linijnij do kilkosti vershin plyus kilkist reber O V E displaystyle O V E Odin z cih algoritmiv Kan 1962 pracyuye vibirayuchi vershini v tomu samomu poryadku sho i vipadkove topologichne sortuvannya Spochatku znahodit nabir pochatkovih vershin yaki ne mayut reber sho vhodyat i vstavlyaye yih v nabir S shonajmenshe odna taka vershina maye isnuvati yaksho graf aciklichnij Todi L Porozhnij spisok sho bude mistiti vidsortovani elementi S Nabir vershin bez reber sho vhodyat doki S ne porozhnye vikonati vidaliti vershinu n z S vstaviti n v L dlya kozhnoyi vershini m z rebrom e z n do m vikonuvati vidaliti rebro e z grafu yaksho m ne maye bilshe reber sho vhodyat todi vstaviti m v S yaksho graf maye rebra todi vivesti povidomlennya pro pomilku graf maye prinajmni odin cikl inakshe vivesti povidomlennya proponovane topologichne sortuvannya L Yaksho mayemo spravu z oriyentovanim aciklichnim grafom to algoritm vidast rishennya ne unikalne Alternativnij algoritm bazuyetsya na poshuku v glibinu Dlya cogo algoritmu rebra vkazuyutsya u zvorotnomu napryamku Tobto yaksho rebro ide z x do y to ce oznachaye sho robota x zalezhit vid roboti y inshimi slovami robota y maye buti zavershena pered tim yak x zmozhe startuvati Algoritm prohodit kozhnu vershinu v grafi v dovilnomu poryadku zapochatkovuyuchi poshuk u glibinu sho zakinchuyetsya koli dosyagaye vershinu yaku vzhe vidvidali z pochatku sortuvannya L Porozhnij spisok sho bude mistiti vidsortovanij nabir vershin S Nabir vsih vershin funkciya vidvidati vershina n yaksho n she ne bula vidvidana todi pomititi n yak vidvidanu dlya kozhnoyi vershini m z rebrom vid n do m vikonati vidvidati m dodati n do L dlya kozhnoyi vershini n v S vikonati vidvidati n ZastosuvannyaZa dopomogoyu topologichnogo sortuvannya buduyetsya korektna poslidovnist vikonannya dij bud yaka z yakih mozhe zalezhati vid inshoyi poslidovnist prohodzhennya navchalnih kursiv studentami zbirki vihidnih tekstiv program za dopomogoyu Makefile iv PrimitkiKahn Arthur B 1962 Topological sorting of large networks Communications of the ACM 5 11 558 562 doi 10 1145 368996 369025PosilannyaNIST Dictionary of Algorithms and Data Structures topological sort Weisstein Eric W TopologicalSort angl na sajti Wolfram MathWorld