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

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

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

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

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

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

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

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

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

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

Пример БФС

В следующем примере 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 можно легко адаптировать для поиска всех решений лабиринта, включая узлы существующего пути в посещаемый набор.