Почему 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 для этой проблемы.

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

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

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

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

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

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

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

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

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

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

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

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

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

    Interesting Posts

    Преобразование Bitmap PixelFormats в C #

    Реляционная алгебра для банковского сценария

    Приемник как внутренний class в Android

    Почему Хаскелл (иногда) называют «Лучшим императивным языком»?

    Периодичность выполнения задачи (один раз в день / раз в неделю)

    Ошибка: com.android.tools.aapt2.Aapt2Exception: ошибка AAPT2: проверить журналы для получения более подробной информации

    Поддерживает ли HTML5 drag and drop загрузки папок или дерева папок?

    Утечка памяти Tomcat Guice / JDBC

    Как вручную установить аутентифицированного пользователя в Spring Security / SpringMVC

    Как установить событие MouseOver / триггер для границы в XAML?

    Ключ Windows продолжает «застревать»,

    Остановите Windows 7 от принудительного отключения при ожидании обновления

    Тип провайдера CodeDom «Microsoft.CodeDom.Providers.DotNetCompilerPlatform.CSharpCodeProvider» не может быть расположен

    Автоматическое управление версиями при изменении файла (изменение / создание / удаление)

    Как добавить событие click в iframe с помощью JQuery

    Давайте будем гением компьютера.