#algorithm #data-structures #graph #depth-first-search #breadth-first-search
Вопрос:
Расписание курсов код доступа: https://leetcode.com/problems/course-schedule/
Эта проблема связана с обнаружением цикла, и если он есть, то вы не сможете пройти весь курс.
Я слышал, что DFS наиболее рекомендуется для обнаружения цикла, но алгоритм Кана рекомендуется для задачи расписания курсов, которая является решением BFS.
Итак … что же это такое? Является ли DFS лучше для обнаружения циклов или это BFS?
Комментарии:
1. Самая большая разница в том, что Хан всегда должен продолжать до конца, DFS может появиться на цикле намного раньше, если таковой имеется. Хороший вопрос в том, кто быстрее, когда нет цикла, и это вопрос качества реализации.
2. Алгоритм Хана не имеет ничего общего с BFS
Ответ №1:
Оба имеют временную сложность O(V E), и оба имеют пространственную сложность O(V E). Так что в этих условиях победителя нет.
Один использует очередь, другой-стек. Один использует градус на узел, другой — отметку посещений на узел.
Одно из отличий заключается в том, что DFS может использовать неявный стек с использованием рекурсии, что может сделать код немного более компактным. Но опять же, вы ограничены доступным пространством стека вызовов, поэтому использование рекурсии может оказаться нецелесообразным решением для больших входных данных, а использование явного стека в конечном итоге может оказаться вариантом для решения на основе DFS.
Так что в целом они получаются равными. Выбирай одно из двух.
Ответ №2:
В реальной работе всегда не рекомендуется использовать O(N) пространство стека, поэтому практические решения на основе DFS будут использовать явный стек.
Реализация явного стека немного сложна, потому что стек-это не просто стек узлов-вам также нужно сохранить текущую позицию в дочернем списке для каждого открытого узла-и логика обхода становится немного сложной.
Решение DFS не является ужасным, но если вы хотите написать хорошее твердое решение, алгоритм Хана в худшем случае окажется проще и быстрее. Он также будет использовать меньше памяти, потому что список ожидающих узлов-это просто список узлов. (Не имеет значения, используете ли вы этот список как стек или очередь. В большинстве случаев использовать его как стек быстрее/проще)
Поэтому, если вы собираетесь явно проверить DAG, чтобы узнать, есть ли в нем циклы, обычно лучше всего использовать алгоритм Хана. Метод DFS полезен, если вы уже выполняете DFS по какой-либо другой причине и хотите обнаружить циклы на этом пути.