Поиск в глубину и ширину: алгоритмы DFS и BFS на Python

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

Что такое DFS и BFS?

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

BFS (Breadth-First Search) - алгоритм поиска в ширину, который исследует граф послойно, сначала посещая все вершины на расстоянии 1, затем на расстоянии 2 и так далее.

Основные различия

Реализация DFS на Python

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

def dfs_recursive(graph, start, visited=None):
    """
    Рекурсивный поиск в глубину
    
    Args:
        graph: словарь со списками смежности
        start: начальная вершина
        visited: множество посещенных вершин
    """
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

Итеративная реализация DFS

def dfs_iterative(graph, start):
    """
    Итеративный поиск в глубину с использованием стека
    
    Args:
        graph: словарь со списками смежности
        start: начальная вершина
    """
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')
            
            # Добавляем соседей в стек (в обратном порядке для правильного обхода)
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

Реализация BFS на Python

from collections import deque

def bfs(graph, start):
    """
    Поиск в ширину с использованием очереди
    
    Args:
        graph: словарь со списками смежности  
        start: начальная вершина
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

Практические примеры

Пример 1: Простой граф

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

print("DFS (рекурсивный):")
dfs_recursive(graph, 'A')
print()

print("DFS (итеративный):")
dfs_iterative(graph, 'A')
print()

print("BFS:")
bfs(graph, 'A')
print()

Возможный вывод:

DFS (рекурсивный): A B D E F C
DFS (итеративный): A B D E F C  
BFS: A B C D E F

Пример 2: Поиск пути между вершинами

def find_path_dfs(graph, start, end, path=[]):
    """
    Поиск пути между двумя вершинами с помощью DFS
    """
    path = path + [start]
    
    if start == end:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in path:
            new_path = find_path_dfs(graph, neighbor, end, path)
            if new_path:
                return new_path
    
    return None

def find_shortest_path_bfs(graph, start, end):
    """
    Поиск кратчайшего пути между двумя вершинами с помощью BFS
    """
    if start == end:
        return [start]
    
    visited = set()
    queue = deque([(start, [start])])
    visited.add(start)
    
    while queue:
        vertex, path = queue.popleft()
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                
                if neighbor == end:
                    return new_path
                
                visited.add(neighbor)
                queue.append((neighbor, new_path))
    
    return None

# Пример использования
print("Путь DFS от A до F:", find_path_dfs(graph, 'A', 'F'))
print("Кратчайший путь BFS от A до F:", find_shortest_path_bfs(graph, 'A', 'F'))

Применение в задачах

Задача 1: Поиск всех компонент связности

def find_connected_components(graph):
    """
    Поиск всех компонент связности в графе
    """
    visited = set()
    components = []
    
    for vertex in graph:
        if vertex not in visited:
            component = []
            dfs_component(graph, vertex, visited, component)
            components.append(component)
    
    return components

def dfs_component(graph, vertex, visited, component):
    """
    Вспомогательная функция для поиска компоненты
    """
    visited.add(vertex)
    component.append(vertex)
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_component(graph, neighbor, visited, component)

# Пример с несвязным графом
disconnected_graph = {
    'A': ['B'], 'B': ['A'],
    'C': ['D'], 'D': ['C'],
    'E': []
}

print("Компоненты связности:", find_connected_components(disconnected_graph))

Задача 2: Обход дерева по уровням

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_traversal(root):
    """
    Обход дерева по уровням (BFS для деревьев)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_values = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_values.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_values)
    
    return result

# Создаем дерево
#     1
#    / \
#   2   3
#  / \
# 4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Обход по уровням:", level_order_traversal(root))
# Вывод: [[1], [2, 3], [4, 5]]

Сложность алгоритмов

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

• DFS: O(V + E), где V - количество вершин, E - количество рёбер
• BFS: O(V + E), где V - количество вершин, E - количество рёбер

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

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

• DFS: O(h), где h - высота дерева/глубина рекурсии
• BFS: O(w), где w - максимальная ширина уровня

Когда использовать DFS и BFS?

Используйте DFS когда:

• Нужно найти любой путь между вершинами
• Требуется топологическая сортировка
• Решаете задачи с backtracking
• Память ограничена (для узких и глубоких графов)

Используйте BFS когда:

• Нужно найти кратчайший путь (в невзвешенном графе)
• Требуется обход по уровням
• Ищете ближайший элемент к стартовой позиции
• Граф широкий и не очень глубокий

Частые ошибки при реализации

1. Забыть пометить вершину как посещенную

# Неправильно - бесконечный цикл
def wrong_dfs(graph, start):
    stack = [start]
    while stack:
        vertex = stack.pop()
        print(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)  # Нет проверки на посещение!

# Правильно
def correct_dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

2. Неправильная обработка пустого графа

def safe_bfs(graph, start):
    if not graph or start not in graph:
        return []
    
    visited = set()
    queue = deque([start])
    # остальная логика...

Заключение

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

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

Дополнительные ресурсы

• LeetCode задачи на DFS и BFS
• Визуализация алгоритмов
• Задачи на графы в CodeForces