Сегодня мы рассмотрим поиск в глубину и поиск в ширину. Никаких особых проблем или чего-то подобного, мы просто реализуем оба этих алгоритма, рассмотрим их и поймем, что именно делает каждый алгоритм и почему мы будем их использовать. Я думаю, это была массовая казнь. Давайте начнем!
Оба алгоритма представляют собой простые алгоритмы построения графиков. Поиск в глубину проверяет один набор ребер на максимальную глубину до тех пор, пока не будут посещены соединительные узлы или пока не останется никаких узлов для посещения. Однако поиск в ширину проверяет каждый слой узлов, действуя как каскад через узлы. DFS обычно реализуется рекурсивно или с использованием стека, а BFS реализуется с использованием очереди.
Для обеих этих реализаций я буду использовать график ниже.
А вот код, изображающий этот график. Это набор словаря узлов: узловых соединений.
Поиск в глубину
Во-первых, мы начнем со старой доброй DFS. Помните, что DFS проверяет настолько глубоко, насколько это возможно, но мы можем навсегда остаться в циклическом круговом обходе, если не будем проводить специальные проверки. Нам нужно проверить, посещали ли мы уже узлы, и посещать ли узлы, которых у нас еще нет, чтобы этого не произошло. Мы будем рассматривать как рекурсивный, так и итерационный алгоритм, а также алгоритм, возвращающий пути.
Вот итеративный алгоритм проверки соединений:
Наш вывод будет включать каждый посещенный узел, то есть каждый узел в нашем графике. Однако, если бы мы создали 2 узла, I и J, которые связаны только друг с другом, он не вернет их, поскольку они не подключены к узлу A.
Вот тот же алгоритм, построенный рекурсивно:
Этот алгоритм создает набор, добавляет в набор посещенные узлы, а затем запускает алгоритм dfs_recursive на следующем узле, который необходимо посетить. Довольно просто.
Теперь мы изменим оба наших алгоритма DFS, чтобы также включить путь от узла A к узлу B (наш начальный и целевой узлы).
Начнем с итеративного подхода:
Это может сбивать с толку, так что давайте разберемся с этим. Сначала мы создаем стек с кортежем (start, [start]). Затем, пока в стеке есть элементы, мы извлекаем верхнее значение и присваиваем вершине и пути первое и второе значения кортежа. Затем для каждого узла, с которым мы сталкиваемся, мы создадим путь, по которому мы туда попали. Однако, если это наш целевой узел, мы выдадим текущий результат. Это просто означает, что мы вернем его, но продолжим цикл, чтобы найти другие пути.
А теперь о рекурсивных путях:
Думаю, намного проще. Также довольно понятно.
Примечание. И yield, и yield из генераторов возврата, поэтому, если вы хотите видеть пути вывода, вам нужно указать Python, чтобы он просматривал их как список ().
Поиск в ширину
Итак, теперь, когда мы знаем, как работать с DFS, давайте взглянем на BFS! Мы будем использовать для этого очередь.
Код почти такой же, за исключением того, что мы используем очередь вместо стека. То же самое и с функцией bfs_paths. Использование очереди приводит к такому каскадному эффекту, когда мы ищем каждый слой, а использование стека приводит к эффекту зондирования, когда мы ищем настолько глубоко, насколько можем.
Это код функции bfs_paths:
Когда использовать что
Как правило, мы будем использовать BFS, чтобы найти кратчайший путь или наименьшее количество шагов для достижения узла цели с учетом начального узла. Мы будем использовать DFS, чтобы найти все возможности от A до B. Если вы хотите проверить, подключены ли 2 узла, вы можете использовать любой из них. НО обычно есть тот, который с большей вероятностью даст лучшую пространственно-временную сложность. Используйте для этого свое усмотрение.
Я также включил несколько ресурсов ниже, где я сам все это узнал.
Ресурсы
- Потрясающее видео с описанием BFS от Minsuk Heo
- Блог Эдда Манна о DFS и BFS
- DFS выполняется без ключевого слова yield
Спасибо за прочтение! Бросьте аплодисменты, если вы узнали что-то новое сегодня! :)
Вы можете проверить код этого блога по кодированию, а также предыдущих, на моем GitHub.
До следующего раза ❤!
