Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
Даешь неделю сортировок на хабре!
Да уж лучше сортировки, чем по неделям мусолить антены у айфонов.
А потом неделю hello world'ов?
Ну ладно, не буду мешать просвящаться…
/me в свое время штудировал algolist.manual.ru
/me в свое время штудировал algolist.manual.ru
А мне понравилось, хоть я и гуманитарий.
Даешь еще!
Даешь еще!
Сразу задачка на этот алгоритм: acm.timus.ru/problem.aspx?space=1&num=1022
На первом курсе написал такой страшный велосипед, чтобы её решить, что даже потом, решая уже топологической сортировкой, не смог его повторить.
На первом курсе написал такой страшный велосипед, чтобы её решить, что даже потом, решая уже топологической сортировкой, не смог его повторить.
Как пример — зависимости в linux :)
это сортировка понравилась мне в свое время тем, что я понял по какой схеме работают некоторые пакетные менеджеры и компиляторы.
ну и на олимпиадах была куча элегантных решений связанных с этим алгоритмом.
спасибо. интересно. познавательно. полезно.
ну и на олимпиадах была куча элегантных решений связанных с этим алгоритмом.
спасибо. интересно. познавательно. полезно.
Хорошо дать мозгам покушать алгоритмы. Я считаю это не напрягом, а наоборот облегчением. Так как не зная алгоритма тратится много времени на придумывание колес, велосипедов, мопедов и прочей техники.
↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.
Опечатка: красим вершину номер 4 в чёрный цвет.
Опечатка: красим вершину номер 4 в чёрный цвет.
При описании алгоритмов было бы хорошо писать их асимптотическую сложность
ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
Никак понять не могу, почему если в стеке они лежат как 2,3,4,1, то достаем мы их и называем как 1,2,3,4?
И почему из вершины номер 4 мы пошли именно в номер 2?
И почему из вершины номер 4 мы пошли именно в номер 2?
Другой подход к решению схожей задачи — тут.
получается что по ссылке в результате мы получаем граф «расплостанный» по уровням, а в реализации через dfs только список вершин(по которому определить что две вершины находятся на одном уровне и их порядок не важен — невозможно).
я прав?
если да то стоит заметить что эти варианты различны по памяти — для варианта dfs нужен список смежности а для того что по ссылке матрица смежности (она больше).
я прав?
если да то стоит заметить что эти варианты различны по памяти — для варианта dfs нужен список смежности а для того что по ссылке матрица смежности (она больше).
Красотишша! А слегка расширив алгоритм до сложности O(v*deg(v)), можно определить, будет ли наш граф циклическим.
Для закрепления такого рода статей, хорошо практически реализовывать алгоритм, скажем, на Тимусе или других сайтах.
Не знаю как не заметили но на последней картинке цифры 2 и 4 поменялись местами
Есть отдельная Unix утилита tsort. Как раз для топологической сортировки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Топологическая сортировка