. Вообще, в ациклическом графе циклов нет по определению. "ациклический" же, т.е. без циклов. Это опечатка же? Вы имели ввиду просто ориентированный граф?
pavlik 322, Потому что это высокоуровневое объяснения сути алгоритма. Для быстрой реализации вам надо поддерживать счетчики входящих ребер и очередь вершин, в которых A(v)=0. Подсчитайте входящие степени. Изначально кладите в очередь все корневые вершины (степень 0). Потом доставайте из очереди вершину, выводите ее в ответ, вычитайте 1 из счетчиков и кладите в очередь те вершины, где счетчики стали 0.
Если делать совсем наивно, то да, там получается еще два цикла.
pavlik 322, Приведите опять код, я запутался. У вас там выше был проход по узлам и потом проход по всем ребрам, а не только по ребрам, выходящим из текущей вершины. В этом ключевая разница. Вы каждое ребро обработаете для каждой вершины. Т.е. получается O(VE) = O(N^3). Если же обходить только ребра исходящие из заданной вершины, то каждое ребро обойдется только один раз.
pavlik 322, Да. Если граф полный (по N-1 ребра у каждого узла), то DFS в нем работает за O(N^2). Быстрее никак. Все ребра все равно придется посмотреть
pavlik 322, Нет, он O(V+E). Внешний цикл по вершинам. Внутри цикл по ребрам исходящим из данной вершины. Поэтому оно обойдет все вершины по одному разу и в каждой обойдет все ребра из нее. Суммарно E ребер.
pavlik 322, Алгоритмам топологической сортировки не надо, чтобы все было одним куском. Конкретно в алгоритме Кана у вас будут вершины без входящих ребер во всех кусках графа. Да, вершины из разных кусков могут в итоге быть в перемешку, но это ничего не портит.
pavlik 322, Можно, конечно, но это в N раз медленнее. Если считать степень, то у вас только один цикл по всем ребрам (или один по вершинам, другой по исходящим ребрам).
pavlik 322, Лучше используйте алгоритм Таръяна тут. Он сразу вам вершины будет снизу вверх выдавать. Как я описывал - функция считает вершину, рекурсивно считая то. что для нее нужно.
Алгоритм Кана работает как обход в ширину - берет сначала те вершины, которые в самом верху. Удаляет их из графа, потом опять берет вершины, которые в самом верху и т.д. Для этого нужна степень, ибо наверху те вершины, у которых входящая степень 0. Без счета степени оно не работает.
Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы
У вас как-то свреху на голову все перевернуто. Для работы алгоритма надо найти "изолированные" узлы, а не в результате его работы вы их находите. Чтобы их найти надо подсчитать степени и пройтись циклом по всем вершинам, иначе никак.
pavlik 322, Потому что это не проще чем просто запустить обход от всех вершин. Ведь вам все равно обычно надо все корневые вершины еще и найти в графе. Так что это такой же цикл по всем вершинам, но при этом надо граф менять и как-то помнить, что вот эта новая вершина корень - фиктивная и где-то дальше ее отдельно обрабатывать.
pavlik 322, Если корневой узел один, то сразу ясно, откуда надо запускаться, и обход обойдет все вершины. Если их несколько, то нет гарантии, что один запуск обойдет все. Поэтому надо будет в цикле обходить все вершины и считать их, если они не подсчитаны.
pavlik 322,
Почитайте статьи про топологическую сортировку, все должно стать понятно.
Или смотрите на это с другой стороны. Функция считает значение в вершине. Если оно было уже подсчитано, то просто возвращает его. Иначе вызывается рекурсивно от всех детей, чтобы подсчитать их, применяет операцию в текущей вершине, сохраняет значение, и возвращает его.
pavlik 322, Для обхода в глубину и для топологической сортировки это не проблема. Раз у вас, судя по некоторым замечаниям, может быть несколько корневых вершин, то у вас будет топологическая сортировка, которая работает через обход в глубину. У вас там будут пометки вершин, в которых вы уже были, и обход не заходит в вершину второй раз.
