Алгоритм поиска в глубину (DFS) на Python

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

К концу этого урока вы узнаете следующее:

• Что такое алгоритм поиска в глубину и как его реализовать с помощью псевдокода

• Как реализовать поиск в глубину в Python с нуля

• Как реализовать алгоритм поиска в глубину на Python с использованием библиотеки NetworkX

Оглавление

• Понимание алгоритма поиска в глубину

• Псевдокод для поиска в глубину

• Реализация поиска в глубину в Python с нуля

• Реализация поиска в глубину в Python с использованием рекурсии

• Реализация поиска в хлебе в Python с использованием NetworkX

• Заключение

Понимание алгоритма поиска в глубину

Алгоритм поиска в глубину является основополагающим алгоритмом для обхода графа. Как следует из названия, он отдает приоритет глубине перед широтой.

Поиск в глубину (DFS) используется в теории графов и алгоритмах для обхода или поиска в структуре графа или дерева, систематически исследуя каждую ветвь как можно глубже перед возвратом назад.

Давайте рассмотрим пример. Представьте, что у нас есть следующий граф, и мы хотим пройти по всем узлам, начиная с узла 'A'.

Для этого создадим два объекта:

1. Стек, для отслеживания добавленных элементов, используя метод последним пришёл - первым ушёл.

2. Множество, для отслеживания уже посещенных узлов

Чтобы начать, давайте сначала отметим нашу начальную вершину как посещённую, добавив её в наш набор посещённых. Затем мы ищем всех её соседей и добавляем их в наш стек.

На изображении выше мы переместили наш посещенный узел в наш набор посещенных узлов. Это позволяет нам убедиться, что мы случайно не посетим его снова. Мы также добавили единственного соседа 'B' в наш стек. На изображении он выделен темным кругом, что указывает на то, что мы знаем, что скоро посетим его.

На следующем шаге мы переходим к B. Удаляя его из нашего стека, мы добавляем его в наш набор посещенных. Затем мы проверяем всех его соседей, которыми в данном случае являются 'C' и 'D', и добавляем их в наш стек.

После этого мы затем берём крайний правый элемент из нашего стека и посещаем его. Мы добавляем его в наш набор посещённых и исследуем все его соседние элементы. Поскольку 'B' был уже посещён, мы не добавляем его в нашу очередь. Вместо этого мы добавляем только 'E' и 'F'.

Мы снова берем самый правый элемент из нашего стека и посещаем его. Мы ищем всех его соседей и добавляем их в наш стек. Поскольку у узла нет соседей, мы затем переходим к следующему элементу в нашем стеке.

Затем мы посещаем 'E', наш самый правый элемент в очереди. Поскольку у 'E' нет соседей, которых мы ещё не посетили, мы не добавляем ничего в стек.

На последнем этапе мы посещаем 'C'. Поскольку у 'F' нет соседей, которых мы еще не видели, наш поиск в глубину здесь заканчивается. Однако можно заметить, что хотя 'C' ранее был соседом, мы посетили его гораздо позже.

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

Псевдокод для поиска в глубину

Псевдокод алгоритма поиска в глубину дает нам крепкую основу для его реализации на Python. Давайте рассмотрим, как выглядит этот псевдокод:

стек = создать пустой стек
пометить startNode как посещенный и поместить его в стек

пока стек не пуст:
     currentNode = извлечь верхний узел из стека
     пометить currentNode как посещенный
    
     для каждого соседа среди соседей currentNode:
         если соседа не посещают:
             отметить соседа как посещённого
             поместить соседа в стек

Давайте разберем, что делает наш псевдокод:

1. Мы создаем стек для хранения наших данных. В Python это может быть простой список.

2. Мы отмечаем нашу начальную вершину как посещенную и помещаем ее в стек.

3. Мы затем создаём цикл while, который выполняется, пока наш стек не пуст. Цикл while берёт верхний элемент из списка и помечает его как текущий узел.

4. Мы затем отмечаем текущий узел как посещённый и рассматриваем каждого соседа, добавляя их в наш стек.

5. Если соседняя вершина не была посещена, мы отмечаем ее как посещенную и добавляем в стек.

Теперь, когда мы знаем, что нам нужно делать, давайте погрузимся в то, как мы можем реализовать это на Python!

Реализация поиска в глубину в Python с нуля

Алгоритм поиска в глубину может показаться немного сложным для реализации на Python. Однако его можно реализовать легко и изящно. Давайте разберем это пошагово и посмотрим, как это сделать.

Мы начнем с реализации нашего графа в виде списка смежности. Это создает словарь, который содержит все узлы нашего графа в качестве ключей. Значения каждого ключа - это список (или множество), который содержит все соседние узлы.

# Представление нашего графа в виде списка смежности
graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
}

Теперь, когда у нас есть наш граф, давайте разработаем функцию для реализации поиска в глубину (DFS) на Python. Наша функция будет принимать два параметра:

1. Наш граф представлен в виде списка смежности.

2. Наш стартовый узел

Давайте посмотрим, как выглядит эта функция:

# Реализация поиска в глубину в Python
def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.add(current_node)
            print(current_node)

            # Добавляем непосещенных соседей в стек
            for neighbor in graph[current_node]:
                if neighbor not in visited:
                    stack.append(neighbor)

Хотя это выглядит как большой объем кода, большая его часть - это комментарии, которые помогут вам понять, что происходит. Давайте разберем это шаг за шагом:

1. Создаем функцию, которая принимает граф (в виде списка смежности) и начальную вершину

2. Сначала создаем множество для хранения посещенных узлов и список, содержащий наш начальный узел.

3. Пока наш стек не пуст (это простой способ проверить, пуст ли список), мы повторяем следующие действия: мы удаляем последний элемент из нашего стека с помощью метода .pop() и обозначаем его как текущий узел. Если узел не входит в наш набор посещенных, тогда мы добавляем его в этот набор.

4. Затем мы проверяем каждого соседа узла. Если сосед не был посещен, мы добавляем его в наш стек.

Давайте теперь реализуем эту функцию и посмотрим, что у нас получится!

# Использование нашей функции поиска в глубину
dfs(graph, 'A')

# Возвращает:
# A
# B
# D
# F
# E
# C

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

Мы можем упростить эту реализацию, используя рекурсию. Давайте рассмотрим это в следующем разделе.

Реализация поиска в глубину в Python с использованием рекурсии

Вы можете упростить реализацию поиска в глубину на Python, используя рекурсию. Здесь возникает компромисс между читаемостью для начинающих программистов и упрощением кода. Ознакомьтесь с функцией ниже, чтобы увидеть, как реализовать DFS рекурсивно на Python:

# Реализация поиска в глубину с использованием рекурсии
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    
    # Выполнить какое-то действие с текущим узлом, например, вывести его
    print(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

В функции, описанной выше, мы сначала определяем функцию dfs_recursive(), которая принимает три параметра: наш граф, нашу начальную вершину и аргумент visited. Функция сначала проверяет, равен ли visited None, что является значением по умолчанию. Если это так, она создает пустое множество. Затем мы добавляем нашу текущую начальную вершину в это множество и выполняем действие с этой вершиной. Затем мы перебираем каждого соседа начальной вершины. Если сосед не был посещен, функция вызывает себя рекурсивно. Это продолжается до тех пор, пока не будет посещено все дерево.

Python обладает множеством отличных библиотек, которые упрощают работу с графами и обход по ним. Давайте рассмотрим NetworkX, которая позволяет нам легче реализовать поиск в глубину.

Реализация поиска в хлебе в Python с использованием NetworkX

Мы можем использовать библиотеку Python NetworkX для реализации поиска в глубину. Поскольку эта библиотека не встроена в Python, сначала нам нужно установить её. Это можно сделать с помощью менеджера пакетов pip, введя показанную ниже команду в ваш терминал:

pip install networkx

NetworkX позволяет легко реализовать графы в Python. Например, вы можете передать список смежности, подобно тому, который мы использовали, чтобы создать объект графа. Давайте посмотрим, как это выглядит:

# Создание объекта графа NetworkX
import networkx as nx
graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
}

G = nx.Graph(graph)
print(G)

# Возвращает: Граф с 6 узлами и 5 ребрами

В приведенном выше блоке кода мы сначала импортировали NetworkX, используя псевдоним nx. Затем мы использовали тот же список смежности для представления нашего графа. Мы передали его в конструктор класса Graph(). Наконец, мы распечатали наш граф, возвращая некоторую общую информацию о графе.

Мы можем использовать несколько различных функций поиска в глубину, которые доступны в библиотеке NetworkX. Чтобы увидеть, как библиотека будет спускаться по нашему графу, мы можем использовать функцию dfs_tree(). Функция проходит по заданному графу, используя предоставленный начальный узел.

# Реализация поиска в ширину (BFS) в NetworkX
bfs = list(nx.bfs_tree(G=G, source='A'))
print(bfs)

# Возвращает: 
# ['A', 'B', 'C', 'D', 'E', 'F']

Мы видим, что если передать наш граф G в функцию вместе с исходным узлом 'A', мы можем получить список, который функция проследует для обхода графа.

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

Заключение

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

В ходе этого урока вы получили представление о следующем:

• Суть алгоритма DFS, от его представления в псевдокоде до реализации на Python.

• Понимание того, как работает DFS, путем систематического изучения узлов и их соседей, используя как итеративные, так и рекурсивные методы.

• Использование библиотеки Python NetworkX для упрощения реализации и обхода графов, демонстрация ее полезности в DFS.

Изучив теорию, разбор псевдокода, ручную реализацию и использование библиотек, вы получили всестороннее понимание алгоритма поиска в глубину (DFS). Вооружившись этими знаниями, вы готовы эффективно применять DFS в различных задачах, связанных с графами, используя как ручные, так и библиотечные подходы в Python.