Pull to refresh

Comments 27

Да уж лучше сортировки, чем по неделям мусолить антены у айфонов.
Ага, прям генератор трендов, созданных и описанных еще до моего рождения :D
А мне понравилось, хоть я и гуманитарий.
Даешь еще!
Сразу задачка на этот алгоритм: acm.timus.ru/problem.aspx?space=1&num=1022
На первом курсе написал такой страшный велосипед, чтобы её решить, что даже потом, решая уже топологической сортировкой, не смог его повторить.
UFO just landed and posted this here
и еще глядя на этот алгоритм можно понять в какой ситуации зависимости не устраняются=)
Да и так, по-моему, понятно: зависимости не устраняются если в графе присутствуют циклы.
это сортировка понравилась мне в свое время тем, что я понял по какой схеме работают некоторые пакетные менеджеры и компиляторы.
ну и на олимпиадах была куча элегантных решений связанных с этим алгоритмом.
спасибо. интересно. познавательно. полезно.
Хорошо дать мозгам покушать алгоритмы. Я считаю это не напрягом, а наоборот облегчением. Так как не зная алгоритма тратится много времени на придумывание колес, велосипедов, мопедов и прочей техники.
↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.

Опечатка: красим вершину номер 4 в чёрный цвет.
Перепроверил — все правильно вроде…
При описании алгоритмов было бы хорошо писать их асимптотическую сложность
ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
Никак понять не могу, почему если в стеке они лежат как 2,3,4,1, то достаем мы их и называем как 1,2,3,4?
И почему из вершины номер 4 мы пошли именно в номер 2?
получается что по ссылке в результате мы получаем граф «расплостанный» по уровням, а в реализации через dfs только список вершин(по которому определить что две вершины находятся на одном уровне и их порядок не важен — невозможно).

я прав?

если да то стоит заметить что эти варианты различны по памяти — для варианта dfs нужен список смежности а для того что по ссылке матрица смежности (она больше).
Да, Вы правы. И что касается результата, и что касается памяти.
Красотишша! А слегка расширив алгоритм до сложности O(v*deg(v)), можно определить, будет ли наш граф циклическим.
Для закрепления такого рода статей, хорошо практически реализовывать алгоритм, скажем, на Тимусе или других сайтах.
Не знаю как не заметили но на последней картинке цифры 2 и 4 поменялись местами

Есть отдельная Unix утилита tsort. Как раз для топологической сортировки.

Sign up to leave a comment.

Articles