BFS и DFS - это методы обхода, используемые при поиске графа. Обход графа - это процесс посещения всех узлов графа. Граф - это группа вершин «V» и ребер «E», соединяющихся с вершинами.
Сравнительная таблица
| Основа для сравнения | BFS | ДФС |
|---|---|---|
| основной | Вершинный алгоритм | Краевой алгоритм |
| Структура данных, используемая для хранения узлов | Очередь | стек |
| Потребление памяти | неэффективный | эффективное |
| Структура построенного дерева | Широкий и короткий | Узкий и длинный |
| Мода обхода | Сначала исследуются самые старые не посещенные вершины. | Вершины по краю исследуются в начале. |
| Оптимальность | Оптимально для поиска кратчайшего расстояния, не по стоимости. | Не оптимальный |
| заявка | Исследует двудольный граф, связную компоненту и кратчайший путь, присутствующий в графе. | Рассматривает двухгранный связный граф, сильно связный граф, ациклический граф и топологический порядок. |
Определение BFS
Поиск в ширину (BFS) - это метод обхода, используемый в графиках. Использует очередь для хранения посещенных вершин. В этом методе акцент делается на вершинах графа, сначала выбирается одна вершина, затем ее посещают и отмечают. Вершины, смежные с посещенной вершиной, затем посещаются и сохраняются в очереди последовательно. Точно так же сохраненные вершины затем обрабатываются одна за другой, и их соседние вершины посещаются. Узел полностью исследуется перед посещением любого другого узла в графе, другими словами, он сначала пересекает самые мелкие неисследованные узлы.
пример
У нас есть граф с вершинами A, B, C, D, E, F, G. Рассматривая A в качестве отправной точки. Шаги, вовлеченные в процесс:
- Вершина А раскрывается и сохраняется в очереди.
- Вершины B, D и G наследники A расширяются и сохраняются в очереди, а вершина A удаляется.
- Теперь B в переднем конце очереди удаляется вместе с сохранением его последующих вершин E и F.
- Вершина D на переднем конце очереди удаляется, а ее связанный узел F уже посещен.
- Вершина G удаляется из очереди, и у нее есть преемник E, который уже посещен.
- Теперь E и F удаляются из очереди, а его последующая вершина C проходит и сохраняется в очереди.
- Наконец C также удаляется, и очередь пуста, что означает, что мы закончили.
- Сгенерированный выход - A, B, D, G, E, F, C.
BFS может быть полезен для определения того, имеет ли граф связанные компоненты или нет. А также он может быть использован при обнаружении двудольного графа .
Граф является двудольным, когда вершины графа разделены на два непересекающихся множества; никакие две соседние вершины не будут находиться в одном наборе. Другой метод проверки двудольного графа - проверить наличие нечетного цикла в графе. Двудольный граф не должен содержать нечетного цикла.
BFS также лучше находит кратчайший путь в графе, который можно рассматривать как сеть.
Определение ДФС
Метод обхода в глубину поиска (DFS) использует стек для хранения посещенных вершин. DFS является методом, основанным на ребре, и работает рекурсивно, когда вершины исследуются вдоль пути (ребра). Исследование узла приостанавливается, как только обнаруживается другой неисследованный узел, и самые глубокие неисследованные узлы пересекаются в первую очередь. DFS проходит / посещает каждую вершину ровно один раз, и каждое ребро проверяется ровно дважды.
пример
Подобно BFS, давайте возьмем тот же график для выполнения операций DFS, а следующие шаги:
- Рассматривая A как начальную вершину, которая исследуется и сохраняется в стеке.
- Последующая вершина B хранится в стеке.
- У вершины B есть два преемника E и F, среди которых в алфавитном порядке E исследуется первым и сохраняется в стеке.
- Преемник вершины E, т. Е. G, хранится в стеке.
- У вершины G есть две соединенные вершины, и обе уже посещены, поэтому G выталкивается из стека.
- Точно так же E s также удалены.
- Теперь вершина B находится на вершине стека, ее другой узел (вершина) F исследуется и сохраняется в стеке.
- У вершины F есть два преемника C и D, между которыми C проходит сначала и сохраняется в стеке.
- У вершины C есть только один предшественник, который уже посещен, поэтому он удаляется из стека.
- Теперь вершина D, соединенная с F, посещается и сохраняется в стеке.
- Поскольку вершина D не имеет никаких не посещенных узлов, следовательно, D удаляется.
- Точно так же F, B и A также появляются.
- Сгенерированный выход - A, B, E, G, F, C, D.
Применение DFS включает проверку двух гранично-связного графа, сильно связного графа, ациклического графа и топологического порядка .
Граф называется двумя ребрами, связанными тогда и только тогда, когда он остается связным, даже если одно из его ребер удалено. Это приложение очень полезно, в компьютерных сетях, где отказ одного звена в сети не повлияет на оставшуюся сеть, и он все равно будет подключен.
Сильно связанный граф - это граф, в котором должен существовать путь между упорядоченной парой вершин. DFS используется в ориентированном графе для поиска пути между каждой упорядоченной парой вершин. DFS может легко решить проблемы с подключением.
Ключевые различия между BFS и DFS
- BFS - это алгоритм на основе вершин, а DFS - алгоритм на основе ребер.
- Структура данных очереди используется в BFS. С другой стороны, DFS использует стек или рекурсию.
- Пространство памяти эффективно используется в DFS, в то время как использование пространства в BFS неэффективно.
- BFS - оптимальный алгоритм, а DFS - не оптимальный.
- DFS строит узкие и длинные деревья. В отличие от BFS строит широкое и короткое дерево.
Заключение
BFS и DFS, оба метода поиска графа имеют одинаковое время выполнения, но разное потребление пространства, DFS занимает линейное пространство, потому что мы должны помнить один путь с неизведанными узлами, в то время как BFS хранит каждый узел в памяти.
DFS дает более глубокие решения и не является оптимальным, но он хорошо работает, когда решение плотное, тогда как BFS является оптимальным, который сначала ищет оптимальную цель.
