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

86

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

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

Ответы:

74

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

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

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

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

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

Марк Байерс
источник
3
(Эффективная память, потому что вы можете вернуться раньше, и ее проще реализовать, потому что вы можете просто позволить стеку позаботиться о хранении открытого списка вместо того, чтобы явно поддерживать его.)
Янтарь,
3
ИМО, это проще, если вы можете полагаться на хвостовую рекурсию.
Хэнк Гей,
2
«снимайте с них отметку при отступлении» - на свой страх и риск! Это может легко привести к поведению O (n ^ 2), в частности, такая DFS будет неправильно понимать перекрестные ребра как ребра "дерева" (ребра "дерева" также будут неправильным употреблением, поскольку они фактически больше не будут формировать дерево)
Димитрис Андреу
1
@Dimitris Andreo: вы можете использовать три посещенных состояния вместо двух для повышения производительности. В ориентированных графах есть разница между «Я видел этот узел раньше» и «Этот узел является частью цикла». С неориентированными графами они эквивалентны.
Марк Байерс,
Собственно, вам определенно нужно третье состояние (чтобы алгоритм был линейным), поэтому вам следует подумать о пересмотре этой части.
Димитрис Андреу
28
  1. DFS проще реализовать
  2. Как только DFS найдет цикл, стек будет содержать узлы, образующие цикл. То же самое не относится к BFS, поэтому вам нужно проделать дополнительную работу, если вы хотите также распечатать найденный цикл. Это делает DFS намного удобнее.
IVlad
источник
11

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

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

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

Димитрис Андреу
источник
4

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

Адитья Раман
источник
Можете ли вы объяснить, как DFS четко определит, что этот цикл не существует в вашем примере. Я согласен с тем, что цикл не существует в приведенном примере. Но если мы перейдем от A-> B, а затем A-> C-> B, мы найдем что B уже был посещен, а его родительский элемент - A, а не C .. и я прочитал, что DFS обнаружит цикл, сравнивая родительский элемент уже посещенного элемента с текущим узлом, с которого мы проверяем в данный момент. Я получаю DFS неправильно или что?
smasher
Все, что вы здесь показали, - это то, что эта конкретная реализация не работает, а не то, что это невозможно с BFS. На самом деле, это возможно, хотя это занимает больше работы и пространство.
Prune
@Prune: Все потоки (я думаю) здесь пытаются доказать, что bfs не будет работать для обнаружения циклов. Если вы знаете, как опровергнуть доказательство, вы должны предоставить доказательство. Просто сказать, что усилий больше, недостаточно
Адитья Раман
Поскольку алгоритм приведен в связанных публикациях, я не считаю целесообразным повторять его здесь.
Prune
Я не мог найти никаких связанных сообщений, поэтому попросил то же самое. Я согласен с вашим мнением о возможностях bfs и только что подумал о реализации. Спасибо за подсказку :)
Адитья Раман
4

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

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

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

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

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

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

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

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

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

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

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

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

Мэтт Тиммерманс
источник
В самом деле, это наиболее (возможно, единственный) связанный ответ здесь, в котором подробно рассматриваются реальные причины.
Plasmacel
2

Если вы поместите цикл в случайное место на дереве, 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 быстрее». Это полностью зависит от ввода, и в этом случае ни один ввод не является более распространенным, чем другой.
IVlad
@Vlad - Цифры не волшебные. Они являются средствами, сформулированы как таковые, и их почти тривиально вычислить с учетом изложенных мной предположений. Если приближение к среднему - плохое приближение, это будет обоснованной критикой. (И я прямо заявил, что если бы вы могли сделать предположения о структуре, ответ мог бы измениться.)
Рекс Керр
числа волшебные, потому что они ничего не значат. Вы взяли случай, когда DFS работает лучше, и экстраполировали эти результаты на общий случай. Ваши утверждения необоснованны: «DFS будет иметь тенденцию попадать в цикл, когда покрывает примерно половину дерева»: докажите это. Не говоря уже о том, что нельзя говорить о циклах в дереве. Дерево по определению не имеет цикла. Я просто не понимаю, о чем вы. DFS будет идти в одном направлении, пока не зайдет в тупик, поэтому у вас нет возможности узнать, какую часть GRAPH (НЕ дерева) он будет исследовать в среднем. Вы просто выбрали случайный случай, который ничего не доказывает.
IVlad
@Vlad - Все нециклические полносвязные неориентированные графы являются (некорневыми неориентированными) деревьями. Я имел в виду «граф, который был бы деревом, если бы не одна ложная ссылка». Возможно, это не главное приложение алгоритма - возможно, вы хотите найти циклы в каком-то запутанном графе, который имеет очень много ссылок, которые делают его не деревом. Но если он древовидный, усредненный по всем графам, любой узел с равной вероятностью может быть источником упомянутой ложной ссылки, что делает ожидаемое покрытие дерева 50% при попадании в ссылку. Так что я согласен с тем, что этот пример не был репрезентативным. Но математика должна быть тривиальной.
Рекс Керр
1

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

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

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

Спайкер
источник
0

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

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

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

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

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

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

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

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

Сообщество
источник
Это совершенно неправильно, поскольку не имеет значения, используете ли вы рекурсию или устраняете рекурсию итерацией. Вы можете реализовать итеративную DFS, которая посещает каждый узел дважды, точно так же, как вы можете реализовать рекурсивный вариант, который посещает каждый узел только один раз.
Plasmacel
0

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

Например:введите описание изображения здесь

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

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

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

Самир
источник