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

Граф - это нелинейная структура данных, которая упорядочивает элементы данных в виде сетевой модели. Узлы в графе называются вершинами, и ребра соединяют эти узлы. Большинство задач с графами можно решить с помощью методов поиска. Часто используемые методы поиска - это поиск в ширину (BFS) и поиск в глубину (DFS). Короче говоря, BFS использует очередь, а DFS - стек.

BFS, DFS

Что такое BFS

BFS означает Дыхание первым поиск. Он использует очередь. Процесс выглядит следующим образом.

Пример следующий.

Рисунок 1: BFS

Предположим, что начальная вершина на изображении выше - 1. Узлы, подключенные к 1, - это 2 и 4. Таким образом, мы можем поместить 1, 2 и 4 в очередь. На выходе будет 1, 2, 4. Для 1 нет оставшихся вершин. Следовательно, мы можем удалить 1 из очереди. Теперь мы можем перейти к 2. Смежные вершины 2 - это 3, 5 и 6. Таким образом, мы можем поместить в очередь 3, 5 и 6. Результатом будет 1, 2, 4, 3, 6. В дополнение к этим трем числам, нет смежных вершин, связанных с 2. Итак, мы можем удалить 2 из очереди. Теперь перейдем к 4. Единственный смежный узел с 4 - 6. Он уже был посещен. Для 4 больше нет вершин, поэтому мы можем удалить 4 из очереди. Вы должны повторять этот процесс, пока очередь не станет пустой. Это указывает на прекращение поисковой операции.

Что такое DFS

DFS означает Поиск в глубину. Процесс выглядит следующим образом.

Посетите соседнюю непосещенную вершину и отметьте ее как посещенную. Затем отобразите его на выходе и вставьте в стек.

Если смежная вершина не найдена, вытащить вершину из стека.

Продолжайте выполнять два вышеуказанных шага, пока стопка не станет пустой.

Рисунок 2: DFS

Начальная вершина - A. Она помещается в стек. Соседние вершины - это B и E. Рассмотрим B. Мы можем поместить B в стек. Поскольку к B нет смежных узлов, мы можем вытолкнуть B из стека. На выходе получается A B. Оставшийся смежный узел с A - это E, поэтому мы можем поместить E в стек. Теперь на выходе получается A B E.

Поскольку к A нет смежных узлов, мы можем извлечь «A» из стека. Смежные узлы для E - это C и H. Теперь рассмотрим C. Мы можем поместить C в стек. Результатом будет A B E C. Процесс продолжается до тех пор, пока стек не станет пустым. Завершает поисковую операцию.

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

Определение

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

Длинная форма

В то время как BFS означает поиск в ширину, DFS означает поиск в глубину.

Метод хранения узлов

Еще одно важное различие между BFS и DFS заключается в том, что BFS использует очередь, а DFS - стек.

Потребление памяти

Метод обхода

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

Заключение

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

Ссылка:

1. Алгоритм поиска в ширину | Псевдокод | Введение, Education 4u, 22 марта 2018 г., доступно здесь 2. Поиск в ширину | Примеры BFS |, Education 4u, 22 марта 2018 г., доступно здесь 3. Алгоритм поиска в глубину | Алгоритм обхода графа |, Education 4u, 22 марта 2018 г., доступно здесь 4. «Алгоритм BFS - Javatpoint». Www.javatpoint.com, доступен здесь 5. «Алгоритм DFS - Javatpoint». Www.javatpoint.com, доступен здесь.