Обход графов: DFS и BFS

🎯 Зачем это нужно?

Представь, что ты создаёшь Instagram и хочешь найти всех друзей друга конкретного пользователя 📱. Или разрабатываешь GPS-навигатор и ищешь кратчайший путь в городе 🗺️. А может, строишь поисковик и обходишь все страницы в интернете? Во всех этих случаях тебе нужны алгоритмы обхода графов!

💼 Google использует обход графов для PageRank 🎮 В играх - поиск пути NPC и ботов 📱 Соцсети - поиск друзей, рекомендации 🧬 Биоинформатика - анализ белковых сетей

📚 История вопроса

Алгоритмы обхода графов появились в 1950-60х годах, но стали популярными благодаря… лабиринтам! 🏰 Тремо (Trémaux) ещё в 1882 году описал правило прохода лабиринта, которое по сути было DFS. А BFS формально описал в 1959 году Эдвард Мур для поиска кратчайшего пути в лабиринте.

Забавный факт: оба алгоритма используют структуры данных, которые работают по принципу “последний пришёл - первый ушёл” (стек) и “первый пришёл - первый ушёл” (очередь) 🥞

💡 Интуиция

DFS (Depth-First Search) - как исследователь пещеры 🕳️ Идёшь вглубь по одному тоннелю, пока не упрёшься в тупик. Тогда возвращаешься назад и пробуешь другой путь. Работает как стопка тарелок - последняя положенная первой берётся.

BFS (Breadth-First Search) - как волна на воде 🌊
Распространяешься равномерно во все стороны. Сначала обходишь всех ближайших соседей, потом соседей соседей. Работает как очередь в кафе - первый пришёл, первый обслужился.

[МЕДИА: image_01] Описание: Сравнение DFS и BFS на простом графе, показывающее порядок обхода вершин Промпт: “educational illustration comparing DFS and BFS graph traversal, side by side graphs showing numbered order of vertex visits, DFS going deep first, BFS spreading level by level, clean modern style with arrows and colors”

📐 Формальное определение

DFS (Поиск в глубину):

• Использует стек (явный или рекурсию)
• Время: O(V + E), память: O(V)
• Идёт максимально глубоко, затем backtrack

BFS (Поиск в ширину):

• Использует очередь
• Время: O(V + E), память: O(V)
• Находит кратчайшие пути в невзвешенном графе

# DFS - рекурсивная версия
def dfs(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(graph, neighbor, visited)

# BFS - итеративная версия
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        print(vertex)  # обрабатываем вершину
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

🔍 Примеры с разбором

Пример 1: Социальная сеть

Граф дружбы: A-B, A-C, B-D, B-E, C-F

DFS от A: A → B → D → E → C → F BFS от A: A → B → C → D → E → F

[МЕДИА: image_02] Описание: Граф социальной сети с пошаговым обходом DFS и BFS Промпт: “social network graph visualization showing friendship connections, step-by-step DFS and BFS traversal with numbered steps and colored paths, modern social media style icons”

Пример 2: Поиск компонент связности

def count_components(graph):
    visited = set()
    components = 0
    
    for vertex in graph:
        if vertex not in visited:
            dfs(graph, vertex, visited)  # или bfs
            components += 1
    
    return components

Применение: Определить количество изолированных групп в соцсети

Пример 3: Кратчайший путь (только BFS!)

def shortest_path(graph, start, end):
    if start == end:
        return [start]
    
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        vertex, path = queue.popleft()
        
        for neighbor in graph[vertex]:
            if neighbor == end:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # путь не найден

🎮 Практика

Базовый уровень 🟢

Задача 1: Дан граф {A:[B,C], B:[A,D], C:[A,E], D:[B], E:[C]}. Выполни DFS от вершины A.

Задача 2: Для того же графа выполни BFS от вершины A.

Задача 3: Сколько компонент связности в графе {1:[2], 2:[1], 3:[4], 4:[3], 5:[]}?

Задача 4: Какой алгоритм найдёт кратчайший путь в невзвешенном графе?

Продвинутый уровень 🟡

Задача 5: Напиши итеративную версию DFS через стек.

Задача 6: Модифицируй BFS для подсчёта расстояния до каждой вершины.

Задача 7: Найди все пути между двумя вершинами (используй DFS).

Задача 8: Определи, является ли граф деревом (связный и без циклов).

Челлендж 🔴

Задача 9: Топологическая сортировка через DFS для направленного ациклического графа.

Задача 10: Найди все мосты в графе (рёбра, удаление которых увеличивает количество компонент).

Задача 11: Реализуй двунаправленный BFS для ускорения поиска пути.

⚠️ Частые ошибки

❌ Ошибка: Забыл отметить стартовую вершину как посещённую в BFS ✅ Правильно: visited.add(start) перед добавлением в очередь 💡 Почему: Иначе можем добавить стартовую вершину в очередь несколько раз

❌ Ошибка: Использую DFS для поиска кратчайшего пути ✅ Правильно: BFS для невзвешенных графов, Dijkstra для взвешенных
💡 Почему: DFS идёт вглубь и может найти очень длинный путь

❌ Ошибка: Не учитываю направленность графа ✅ Правильно: В направленном графе A→B не означает B→A 💡 Почему: Обход может “застрять” в односторонней части

❌ Ошибка: Переполнение стека в рекурсивном DFS ✅ Правильно: Используй итеративную версию для больших графов 💡 Почему: Python имеет ограничение глубины рекурсии ~1000

❌ Ошибка: Не проверяю на посещённость перед добавлением в очередь/стек ✅ Правильно: Проверка visited перед добавлением, не при извлечении 💡 Почему: Экономим память и избегаем дубликатов

🎓 Главное запомнить

✅ DFS = стек (рекурсия), идёт вглубь, O(V+E) ✅ BFS = очередь, идёт вширь, находит кратчайшие пути
✅ Оба работают за линейное время от размера графа

🔗 Связь с другими темами

Откуда пришли: Представление графов (урок 260) Куда ведут: Алгоритм Дейкстры, поиск компонент сильной связности, топологическая сортировка, поиск циклов, планарность графов