BFS против DFS – разница между ними

Что такое БФС?

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

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

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

Что такое ДФС?

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

Разница между двоичным деревом BFS и DFS

Вот важные различия между BFS и DFS.

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

Пример БФС

В следующем примере BFS мы использовали граф, имеющий 6 вершин.

Пример БФС

Шаг 1)

У вас есть график из семи чисел в диапазоне от 0 до 6.

Шаг 2)

0 или ноль был помечен как корневой узел.

Шаг 3)

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

Шаг 4)

Остальные 0 соседних и непосещенных узлов посещаются, помечаются и вставляются в очередь.

Шаг 5)

Итерации обхода повторяются до тех пор, пока не будут посещены все узлы.

Пример ДФС

В следующем примере DFS мы использовали неориентированный граф, имеющий 5 вершин.

Шаг 1)

Мы начали с вершины 0. Алгоритм начинается с помещения ее в список посещенных и одновременного помещения всех ее смежных вершин в список структура данных называется стеком.

Шаг 2)

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

Шаг 3)

У вершины 2 есть непосещенная соседняя вершина из вершины 4. Поэтому мы добавляем ее в стек и посещаем ее.

Шаг 4)

Наконец, мы посетим последнюю вершину 3, у нее нет непосещенных соседних узлов. Мы завершили обход графа с помощью алгоритма DFS.

Приложения BFS

Вот приложения BFS:

Невзвешенные графики

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

P2P-сети

BFS может быть реализована для обнаружения всех ближайших или соседних узлов в одноранговой сети. Это позволит быстрее найти необходимые данные.

Веб-краулеры

Поисковые системы или веб-сканеры могут легко создавать несколько уровней индексов, используя BFS. Реализация BFS начинается с источника, которым является веб-страница, а затем посещаются все ссылки из этого источника.

Сетевое вещание

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

Приложения DFS

Вот важные приложения DFS:

Взвешенный график

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

Обнаружение цикла на графике

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

Найти путь

Мы можем специализироваться на алгоритме DFS для поиска пути между двумя вершинами.

Топологическая сортировка

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

Поиск сильно связанных компонентов графа

Он используется в графе DFS, когда существует путь от каждой вершины графа к другим оставшимся вершинам.

Решение головоломок только с одним решением

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