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

7.1 Принципы работы алгоритма DFS

Поиск в глубину (Depth-First Search, DFS) — это алгоритм обхода или поиска в графе. Он начинает с начальной вершины и идёт вглубь графа, пока не достигнет вершины без непосещённых соседей, затем возвращается назад и продолжает процесс с другими вершинами.

Шаги алгоритма:

1. Начинаем с выбранной начальной вершины и помечаем её как посещённую.
2. Исследуем первую непосещённую соседнюю вершину.
3. Повторяем шаги 1 и 2 для этой соседней вершины.
4. Если все соседи текущей вершины посещены, возвращаемся назад (backtrack) к предыдущей вершине и продолжаем процесс.
5. Процесс повторяется до тех пор, пока не будут посещены все вершины, достижимые из начальной вершины.

Визуализация:

Временная и пространственная сложность DFS:

Временная сложность:

O(V + E), где V — количество вершин, E — количество рёбер.

Каждый узел и каждое ребро графа посещаются один раз.

Пространственная сложность:

O(V), так как используется стек вызовов или явный стек для хранения вершин, а также массивы для хранения состояния (посещённые вершины).

7.2 Реализация DFS с использованием рекурсии

Давайте для начала реализуем DFS с использованием рекурсии — код будет красивым и компактным.

Рекурсивная реализация DFS:

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)
    
# Пример использования:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Реализация DFS с использованием стека

Без рекурсии код будет немного длиннее, так как нам нужно дополнительно хранить список посещённых вершин.

Итеративная реализация DFS (с использованием стека):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Обработка узла
        
            for neighbor in reversed(graph[vertex]):  # Обратный порядок для правильного порядка обхода
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Пример использования:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Примеры задач, решаемых с использованием DFS

Классические примеры задач, решаемых с использованием DFS:

1. Поиск пути в лабиринте:

Используется для нахождения пути в лабиринте от начальной до конечной точки.

Применение:

В видеоиграх и робототехнике для навигации по лабиринтам и сложным пространствам.

2. Проверка связности графа:

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

Применение:

В сетевом анализе для проверки связности сети.

3. Топологическая сортировка:

Используется для упорядочивания вершин ориентированного ациклического графа (DAG) таким образом, что для любого ребра (u, v) вершина u предшествует вершине v.

Применение:

В компиляторах для упорядочивания зависимостей и задач.

4. Обнаружение циклов в графе:

Проверка, содержит ли граф циклы.

Применение:

В анализе зависимостей для обнаружения циклических зависимостей.

5. Генерация лабиринтов:

Использование DFS для генерации случайных лабиринтов.

Применение:

В игровых и развлекательных приложениях для создания лабиринтов.