Разница между BFS и DFS

BFS против DFS

Поиск в ширину (также известный как BFS) - это метод поиска, используемый для расширения всех узлов конкретного графа. Он выполняет эту задачу путем поиска каждого решения, чтобы исследовать и расширить эти узлы (или комбинацию последовательностей в них). Таким образом, BFS не использует эвристический алгоритм (или алгоритм, который ищет решение по нескольким сценариям). После того как все узлы получены, они добавляются в очередь, известную как очередь First In, First Out. Те узлы, которые не были исследованы, «хранятся» в контейнере, помеченном как «открытый»; после изучения они транспортируются в контейнер с пометкой «закрыто».

Поиск в глубину (также известный как DFS) - это метод поиска, который углубляется в дочерний узел поиска до тех пор, пока не будет достигнута цель (или пока не будет найден узел без каких-либо других перестановок или «потомков»). После того, как одна цель найдена, поиск возвращается к предыдущему узлу, у которого есть решение, повторяя процесс до тех пор, пока все узлы не будут успешно найдены. Таким образом, узлы продолжают откладываться для дальнейшего исследования - это называется нерекурсивной реализацией.

Особенности BFS - это сложность пространства и времени, полнота, доказательство полноты и оптимальность. Пространственная сложность относится к пропорции числа узлов на самом глубоком уровне поиска. Сложность времени относится к фактическому количеству «времени», используемому для рассмотрения каждого пути, по которому будет проходить узел при поиске. Полнота - это, по сути, поиск, который находит решение в графе независимо от того, какой это граф. Доказательством полноты является самый мелкий уровень, на котором цель находится в узле на определенной глубине. Наконец, оптимальность относится к BFS, которая не взвешена - это график, используемый для стоимости за единицу измерения..

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

Резюме:

1. BFS ищет каждое решение в графе, чтобы расширить его узлы; DFS копается глубоко внутри дочернего узла, пока не будет достигнута цель.

2. Особенности BFS: сложность пространства и времени, полнота, доказательство полноты и оптимальность; наиболее естественный вывод для DFS - остовное дерево с тремя классами: передние ребра, задние ребра и поперечные ребра.