Преимущественно DFS используется для нахождения цикла в графах, а не в BFS. Любые причины? Оба могут найти, если узел уже прошел , посетив при обходе дерева/графика.Почему DFS, а не BFS для нахождения цикла в графиках
Глубина первого поиска - более эффективная память, чем первый поиск по ширине, так как вы можете вернуться назад. Это также проще реализовать, если вы используете стек вызовов, но это зависит от самого длинного пути, не переполняющего стек.
Также, если ваш график directed, то вам нужно не просто помнить, если вы посетили узел или нет, но и как вы туда попали. В противном случае вы можете подумать, что нашли цикл, но на самом деле все, что у вас есть, это два отдельных пути A-> B, но это не значит, что существует путь B-> A. Например, 
Если вы BFS, начиная с 0, он обнаружит, как цикл присутствует, но на самом деле нет никакого цикла.
С первым поиском глубины вы можете отмечать узлы как посещенные, как вы опускаетесь, и отбрасывать их, как вы назад. См. Комментарии для улучшения производительности по этому алгоритму.
Для best algorithm for detecting cycles in a directed graph вы можете посмотреть Tarjan's algorithm.
(Память эффективна, потому что вы быстрее возвращаетесь назад и проще реализовать, потому что вы можете просто позволить стеку заботиться о сохранении открытого списка вместо того, чтобы явно его поддерживать.) – Amber
IMO, это проще, если вы можете положиться на хвост рекурсии. –
+1 для указания сценария двойного пути. –
Если вы поместите цикл в случайное пятно на дереве, 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
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 четко определит, что цикл не существует в вашем примере. Я согласен, что цикл не существует в приведенном примере. Но если мы перейдем от A-> B, а затем A-> C-> B, мы что B уже был посещен, а его родительский элемент A не C..и читал, что DFS будет определять цикл, сравнивая родительский элемент уже посещенного элемента с текущим узлом, из которого мы проверяем в этот момент. или что? – smasher
Все, что вы показали здесь, это то, что эта конкретная реализация не работает, а не то, что с BFS это невозможно. Фактически, это * возможно *, хотя требуется больше работы и пространства. – Prune
@Prune: Все потоки (я думаю) здесь пытаются доказать, что bfs не будут работать для обнаружения циклов. Если вы знаете, как противодействовать доказательству, вы должны дать доказательство. Просто говоря, что усилия больше не достаточны –
Чтобы доказать, что график является циклическим, вам просто нужно доказать, что он имеет один цикл (край указывает на себя прямо или косвенно).
В DFS мы берем одну вершину за раз и проверяем, имеет ли она цикл. Как только будет найден цикл, мы можем опустить проверку других вершин.
В BFS нам нужно отслеживать множество вершинных ребер одновременно, а чаще всего в конце вы узнаете, имеет ли он цикл. По мере роста размера графика BFS требует больше пространства, вычислений и времени по сравнению с DFS.
Это зависит от того, если вы говорите об рекурсивных или итеративных реализациях.
Рекурсивно-DFS посещает каждый узел дважды. Итеративно-BFS посещает каждый узел один раз.
Если вы хотите обнаружить цикл, вам необходимо исследовать узлы как до, так и после добавления их смещений - как при запуске на узле, так и при завершении работы с узлом.
Для этого требуется больше работы в Iterative-BFS, поэтому большинство людей выбирает Recursive-DFS.
Обратите внимание, что простая реализация Iterative-DFS с, скажем, std :: stack имеет ту же проблему, что и Iterative-BFS. В этом случае вам нужно поместить фиктивные элементы в стек, чтобы отслеживать, когда вы «завершаете» работу над узлом.
Смотрите этот ответ для получения более подробной информации о том, как итерационно-DFS требует дополнительной работы, чтобы определить, когда вы «конец» с узлом (ответил в контексте TopoSort):
Topological sort using DFS without recursion
Надеется, что объясняет, почему люди предпочитают Recursive-DFS для проблем, когда вам нужно определить, когда вы «закончите» обработку узла.
Является ли ваш график направленным или неориентированным? –
В ориентированных графиках для определения цикла может использоваться только DFS; но в Undirected графах можно использовать оба. – Hengameh