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

Ответ 1

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

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

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

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

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

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

Ответ 8

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

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

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

1. Вершина запускается

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

3. Вершина закончена.

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

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

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

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

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

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

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