Алгоритми пошуку в глибину (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 для генерації випадкових лабіринтів.

Застосування:

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