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

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

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

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

Если вы выполните BFS, начиная с 0, он определит, что цикл присутствует, но на самом деле цикла нет.

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

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

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

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

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

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

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

Я не знаю, почему в моей ленте появился такой старый вопрос, но все предыдущие ответы плохие, так что ...

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

В DFS каждая вершина посещается, где посещение вершины означает:

1. Вершина запущена

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

3. Вершина готова.

Важнейшей особенностью является то, что все ребра, достижимые из вершины, отслеживаются до того, как вершина будет завершена. Это особенность DFS, но не BFS. Фактически это определение DFS.

Благодаря этой функции мы знаем, что когда запускается первая вершина в цикле:

1. Ни один из ребер цикла не прослежен. Мы знаем это, потому что вы можете добраться до них только из другой вершины в цикле, и мы говорим о первой вершине, которая будет запущена.
2. Все неотслеживаемые ребра, достижимые из этой вершины, будут отслежены до ее завершения, включая все ребра в цикле, поскольку ни одно из них еще не было отслежено. Следовательно, если есть цикл, мы найдем ребро обратно к первой вершине после его запуска, но до его завершения; и
3. Поскольку все отслеживаемые ребра достижимы из каждой запущенной, но незавершенной вершины, нахождение ребра в такой вершине всегда указывает на цикл.

Итак, если есть цикл, то мы гарантированно найдем ребро к запущенной, но незавершенной вершине (2), а если мы найдем такое ребро, то нам гарантировано, что цикл (3) существует.

Вот почему DFS используется для поиска циклов в ориентированных графах.

BFS таких гарантий не дает, поэтому просто не работает. (несмотря на очень хорошие алгоритмы поиска циклов, которые включают BFS или аналогичные в качестве подпроцедуры)

С другой стороны, неориентированный граф имеет цикл всякий раз, когда есть два пути между любой парой вершин, т. Е. Когда это не дерево. Это легко обнаружить во время BFS или DFS - ребра, отслеживаемые до новых вершин, образуют дерево, а любое другое ребро указывает на цикл.

Если вы поместите цикл в случайное место на дереве, 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 дает вам преимущество).

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

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

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

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

Рекурсивный DFS посещает каждый узел дважды. Итеративная BFS посещает каждый узел один раз.

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

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

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

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

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

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

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

Например:

Если данный узел равен 2, есть три цикла, в которых он является частью - [2,3,4], [2,3,4,5,6,7,8,9]& [2,5,6,7,8,9]. Самый короткий[2,3,4]

Для реализации этого с помощью BFS вы должны явно поддерживать историю посещенных узлов, используя надлежащие структуры данных.

Но для всех других целей (например: найти какой-либо циклический путь или проверить, существует ли цикл или нет), DFSэто очевидный выбор по причинам, указанным другими.