MaxRokatansky Apr 26 2020 at 16:32

Топологическая сортировка

6 min

36K

OTUS corporate blogProgramming*Algorithms*

Translation

Comments 5

nightvich Apr 26 2020 at 22:24

Была однажды задача по перебсорке большого количества java пакетов, которые зависимы друг от друга. Собирать надо было а изолированном окружении за один проход. Для этого использовал топологическую сортировку по алгоритму Тарьяна. За перевод спасибо.

malkovsky Apr 27 2020 at 03:10

Хмм… скорее всего это ровно то, что рассказывается в статье, уверен, что это фольклор. Тарьян вообще кучу всего придумал, наиболее близкое по теме — это скорее всего алгоритм нахождения компонент сильной связности, если применить его к ациклическому графу, то он сделает на нем топологическую сортировку, а потом обнаружит, что все компоненты состоят из одной вершины.

nightvich Apr 27 2020 at 03:19

Да, вроде он.
Вот тут хорошее описание.

bonta Nov 17 2021 at 15:45

Наверное это лучшее объяснение топологической сортировки для обычных программистов.

Спасибо за перевод.

aabzel Jun 3 at 12:33

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