Почему DFS, а не BFS для нахождения цикла в графах

Question

Преимущественно DFS используется для нахождения цикла в графиках, а не BFS. Какие-либо причины? Оба могут найти, если узел уже был посетил при обходе дерева / графика.

Answer 1

Поиск в глубину в первую очередь эффективнее, чем поиск в ширину, поскольку вы можете вернуться назад быстрее. Это также легче реализовать, если вы используете стек вызовов, но это зависит от самого длинного пути, не переполняющего стек.

Также, если ваш график направлен , вам нужно не только запомнить, посещали ли вы узел или нет, но и то, как вы туда попали. В противном случае вы можете подумать, что нашли цикл, но на самом деле все, что у вас есть, это два отдельных пути A-> B, но это не значит, что есть путь B-> A. Например,

Если вы выполняете BFS, начиная с 0, он будет обнаруживать наличие цикла, но фактически его нет.

При первом глубинном поиске вы можете пометить узлы как посещенные при спуске и отменить их при возврате. См. Комментарии для улучшения производительности этого алгоритма.

Для лучшего алгоритма для обнаружения циклов в ориентированном графе вы можете взглянуть на Алгоритм Тарьяна .

Answer 2

1. DFS проще в реализации
2. Как только DFS найдет цикл, стек будет содержать узлы, формирующие цикл. То же самое не относится к BFS, поэтому вам нужно проделать дополнительную работу, если вы хотите распечатать найденный цикл. Это делает DFS намного удобнее.

Answer 3

BFS может быть разумным, если график не является ненаправленным (будь моим гостем в демонстрации эффективного алгоритма, использующего BFS, который будет сообщать о циклах в ориентированном графе!), Где каждый «край ребра» определяет цикл. Если поперечный край равен {v1, v2}, а корень (в дереве BFS), содержащий эти узлы, равен r, то цикл равен r ~ v1 - v2 ~ r (~ - это путь, - - одно ребро), о котором можно сообщить почти так же легко, как в DFS.

Единственная причина для использования BFS может быть в том случае, если вы знаете, что у вашего (ненаправленного) графа будут длинные и малые пути (другими словами, глубокие и узкие). В этом случае BFS потребует пропорционально меньше памяти для своей очереди, чем стек DFS (оба, конечно, все еще линейные).

Во всех других случаях DFS явно выигрывает. Он работает как с ориентированными, так и с ненаправленными графами, и тривиально сообщать о циклах - просто конкатенируйте любой задний край к пути от предка к потомок, и вы получите цикл. В общем, гораздо лучше и практичнее, чем BFS для этой проблемы.

Answer 4

BFS не будет работать для ориентированного графа при поиске циклов. Рассмотрим A-> B и A-> C-> B как пути от A до B в графе. BFS скажет, что после прохождения одного из путей, которые посещают B. Продолжая двигаться по следующему пути, он скажет, что отмеченный узел B был снова найден, следовательно, существует цикл. Очевидно, что здесь нет цикла.

Answer 5

Если вы поместите цикл в случайное место на дереве, DFS будет стремиться попасть в цикл, когда он покрыт примерно половиной дерева, и половину времени он уже пройдёт туда, где проходит цикл, и половину времени не будет (и найдет его в среднем в половине дерева), поэтому он оценит в среднем около 0,5 * 0,5 + 0,5 * 0,75 = 0,625 дерева.

Если вы поместите цикл в случайное место на дереве, BFS будет стремиться попасть в цикл только тогда, когда он оценивает слой дерева на этой глубине. Таким образом, вам обычно приходится оценивать листья двоичного дерева баланса, что обычно приводит к оценке большего количества дерева. В частности, в 3/4 времени по крайней мере одна из двух ссылок появляется в листьях дерева, и в этих случаях вы должны оценивать в среднем 3/4 дерева (если есть одна ссылка) или 7 / 8 дерева (если их два), так что вы уже ожидаете поиска 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0,656 ... от дерева, даже не добавляя стоимость поиска дерева с циклом, добавленным от узлов листа.

Кроме того, DFS проще в реализации, чем BFS. Поэтому его следует использовать, если вы ничего не знаете о своих циклах (например, циклы, вероятно, находятся рядом с корнем, из которого вы выполняете поиск, и в этот момент BFS дает вам преимущество).

Answer 6

Чтобы доказать, что граф является циклическим, вам просто нужно доказать, что у него есть один цикл (ребро направлено на себя прямо или косвенно).

В DFS мы берем одну вершину за раз и проверяем, есть ли у нее цикл. Как только цикл найден, мы можем не проверять другие вершины.

В BFS нам нужно отслеживать множество ребер вершин одновременно, и чаще всего в конце вы узнаете, есть ли у него цикл. По мере роста размера графика BFS требует больше места, вычислений и времени по сравнению с DFS.

Answer 7

Это зависит от того, говорите ли вы о рекурсивных или итеративных реализациях.

Recursive-DFS посещает каждый узел дважды. Iterative-BFS посещает каждый узел один раз.

Если вы хотите обнаружить цикл, вам нужно исследовать узлы как до, так и после добавления их смежностей - как при «запуске» на узле, так и при «завершении» с узлом.

Это требует больше работы в Iterative-BFS, поэтому большинство людей выбирают Recursive-DFS.

Обратите внимание, что простая реализация Iterative-DFS с, скажем, std :: stack имеет ту же проблему, что и Iterative-BFS. В этом случае вам необходимо поместить фиктивные элементы в стек, чтобы отслеживать, когда вы «закончите» работу над узлом.

См. Этот ответ для более подробной информации о том, как Iterative-DFS требует дополнительной работы, чтобы определить, когда вы «закончите» с узлом (ответ в контексте TopoSort):

Топологическая сортировка с использованием DFS без рекурсии

Надеюсь, это объясняет, почему люди предпочитают Recursive-DFS для проблем, когда вам нужно определить, когда вы «закончите» обработку узла.