Что такое BFS?
BFS - это алгоритм, который используется для графического отображения данных, поиска в дереве или обхода структур. Алгоритм эффективно посещает и помечает все ключевые узлы на графике точным образом по ширине.
Этот алгоритм выбирает один узел (начальную или исходную точку) в графе, а затем посещает все узлы, смежные с выбранным узлом. Как только алгоритм посещает и отмечает начальный узел, он перемещается к ближайшим непосещенным узлам и анализирует их.
После посещения все узлы помечаются. Эти итерации продолжаются до тех пор, пока все узлы графа не будут успешно посещены и отмечены. Полная форма BFS - это поиск в ширину.
В этом BSF Vs. В руководстве по бинарному дереву DFS вы узнаете:
- Что такое BFS?
- Что такое DFS?
- Пример BFS
- Пример DFS
- Разница между двоичным деревом BFS и DFS
- Приложения BFS
- Приложения DFS
Что такое DFS?
DFS - это алгоритм поиска или обхода графов или деревьев в направлении глубины. Выполнение алгоритма начинается с корневого узла и исследует каждую ветвь перед возвратом. Он использует структуру данных стека для запоминания, получения следующей вершины и начала поиска всякий раз, когда на любой итерации появляется тупик. Полная форма DFS - поиск в глубину.
Пример BFS
В следующем примере DFS мы использовали граф с 6 вершинами.
Пример BFS
Шаг 1)
У вас есть график из семи чисел в диапазоне от 0 до 6.
Шаг 2)
0 или ноль был отмечен как корневой узел.
Шаг 3)
0 посещается, помечается и вставляется в структуру данных очереди.
Шаг 4)
Оставшиеся 0 соседних и непосещенных узлов посещаются, помечаются и вставляются в очередь.
Шаг 5)
Итерации обхода повторяются до тех пор, пока не будут посещены все узлы.
Пример DFS
В следующем примере DFS мы использовали неориентированный граф с 5 вершинами.
Шаг 1)
Мы начали с вершины 0. Алгоритм начинается с помещения ее в список посещенных и одновременного помещения всех смежных вершин в структуру данных, называемую стеком.
Шаг 2)
Вы посетите элемент, который находится наверху стека, например, 1, и перейдете к его соседним узлам. Это потому, что 0 уже был посещен. Поэтому посещаем вершину 2.
Шаг 3)
В вершине 2 есть непосещенная ближайшая вершина в 4. Поэтому мы добавляем ее в стек и посещаем ее.
Шаг 4)
Наконец, мы посетим последнюю вершину 3, у нее нет непосещаемых смежных узлов. Мы завершили обход графа с использованием алгоритма DFS.
Разница между двоичным деревом BFS и DFS
| BFS | DFS |
| BFS находит кратчайший путь к месту назначения. | DFS переходит в конец поддерева, а затем выполняет возврат. |
| Полная форма BFS - это поиск в ширину. | Полная форма DFS - это поиск в глубину. |
| Он использует очередь, чтобы отслеживать следующее место для посещения. | Он использует стек, чтобы отслеживать следующее место для посещения. |
| BFS проходит согласно уровню дерева. | DFS проходит согласно глубине дерева. |
| Это реализовано с использованием списка FIFO. | Это реализовано с использованием списка LIFO. |
| Для этого требуется больше памяти по сравнению с DFS. | Он требует меньше памяти по сравнению с BFS. |
| Этот алгоритм дает решение с наиболее мелким путем. | Этот алгоритм не гарантирует решения по самому мелкому пути. |
| В BFS нет необходимости в возврате. | В DFS есть необходимость в возврате. |
| Вы никогда не попадете в ловушку конечных циклов. | Вы можете попасть в бесконечные петли. |
| Если вы не нашли никакой цели, возможно, вам придется расширить множество узлов, прежде чем будет найдено решение. | Если вы не найдете никакой цели, может произойти возврат листового узла. |
Приложения BFS
Вот приложения BFS:
Невзвешенные графики:
Алгоритм BFS может легко создать кратчайший путь и минимальное остовное дерево для посещения всех вершин графа в кратчайшие сроки с высокой точностью.
P2P сети:
BFS может быть реализован для обнаружения всех ближайших или соседних узлов в одноранговой сети. Это позволит быстрее найти нужные данные.
Веб-сканеры:
Поисковые системы или веб-сканеры могут легко создавать несколько уровней индексов, используя BFS. Реализация BFS начинается с источника, которым является веб-страница, а затем посещаются все ссылки из этого источника.
Сетевое вещание:
Широковещательный пакет управляется алгоритмом BFS, чтобы найти и достичь всех узлов, для которых он имеет адрес.
Приложения DFS
Вот важные приложения DFS:
Взвешенный график:
В взвешенном графе обход графа DFS генерирует дерево кратчайших путей и минимальное остовное дерево.
Обнаружение цикла на графике:
У графа есть цикл, если мы нашли задний край во время DFS. Следовательно, мы должны запустить DFS для графа и проверить наличие задних ребер.
Найти путь:
Мы можем специализироваться на алгоритме DFS для поиска пути между двумя вершинами.
Топологическая сортировка:
Он в основном используется для планирования заданий на основе заданных зависимостей между группой заданий. В информатике он используется при планировании инструкций, сериализации данных, логическом синтезе, определении порядка выполнения задач компиляции.
Поиск сильно связанных компонентов графа:
Он используется в графе DFS, когда есть путь от каждой вершины в графе к другим оставшимся вершинам.
Решение головоломок одним решением:
Алгоритм DFS можно легко адаптировать для поиска всех решений лабиринта, включив узлы на существующем пути в посещаемый набор.
КЛЮЧЕВЫЕ ОТЛИЧИЯ:
- BFS находит кратчайший путь к месту назначения, тогда как DFS идет к нижней части поддерева, а затем выполняет возврат.
- Полная форма BFS - это поиск в ширину, а полная форма DFS - это поиск в глубину.
- BFS использует очередь, чтобы отслеживать следующее место для посещения. тогда как DFS использует стек для отслеживания следующего места для посещения.
- BFS проходит в соответствии с уровнем дерева, а DFS проходит в соответствии с глубиной дерева.
- BFS реализуется с использованием списка FIFO, с другой стороны, DFS реализуется с использованием списка LIFO.
- В BFS вы никогда не можете попасть в конечные циклы, тогда как в DFS вы можете попасть в бесконечные циклы.