DFS: Задачи на графы

Обход графов с помощью DFS. Клонирование, цикл, топологическая сортировка.

#1. Clone Graph (LeetCode 133) 🟦 Medium

Ссылка: https://leetcode.com/problems/clone-graph/

Условие: Создать глубокую копию графа.

Решение:

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node:
        return None

    old_to_new = {}

    def dfs(n):
        if n in old_to_new:
            return old_to_new[n]

        copy = Node(n.val)
        old_to_new[n] = copy

        for neighbor in n.neighbors:
            copy.neighbors.append(dfs(neighbor))

        return copy

    return dfs(node)

Объяснение:

Словарь old_to_new хранит соответствие оригинал → копия
DFS создаёт копию узла, затем рекурсивно копирует соседей

Сложность: O(n)

#2. Course Schedule (LeetCode 207) 🟦 Medium

Ссылка: https://leetcode.com/problems/course-schedule/

Условие: Можно ли пройти все курсы, заданы ли пререквизиты (граф зависимостей)?

Решение:

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # 0 = не посещён, 1 = в процессе, 2 = завершён
    state = [0] * numCourses

    def has_cycle(course):
        if state[course] == 1:  # Обнаружили цикл
            return True
        if state[course] == 2:  # Уже обработан
            return False

        state[course] = 1  # В процессе

        for neighbor in graph[course]:
            if has_cycle(neighbor):
                return True

        state[course] = 2  # Завершён
        return False

    for course in range(numCourses):
        if has_cycle(course):
            return False

    return True

Объяснение:

Три состояния: 0 (new), 1 (visiting), 2 (visited)
Если встретили узел в состоянии 1 — цикл

Сложность: O(V + E)

#3. Course Schedule II (LeetCode 210) 🟦 Medium

Ссылка: https://leetcode.com/problems/course-schedule-ii/

Условие: Верните порядок прохождения курсов.

Решение (DFS версия):

def findOrder(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    result = []
    state = [0] * numCourses  # 0, 1, 2

    def dfs(course):
        if state[course] == 1:
            return False  # Цикл
        if state[course] == 2:
            return True  # Уже обработан

        state[course] = 1

        for neighbor in graph[course]:
            if not dfs(neighbor):
                return False

        state[course] = 2
        result.append(course)
        return True

    for course in range(numCourses):
        if not dfs(course):
            return []

    return result

Сложность: O(V + E)

#4. All Paths From Source to Target (LeetCode 797) 🟦 Medium

Ссылка: https://leetcode.com/problems/all-paths-from-source-to-target/

Условие: Дан ациклический граф. Найти все пути от 0 до n-1.

Решение:

def allPathsSourceTarget(graph):
    result = []

    def dfs(node, path):
        if node == len(graph) - 1:
            result.append(path[:])
            return

        for neighbor in graph[node]:
            path.append(neighbor)
            dfs(neighbor, path)
            path.pop()  # Backtrack

    dfs(0, [0])
    return result

Объяснение:

path[:] создаёт копию списка
path.pop() — backtrack

Сложность: O(2^n × n)

#5. Path Sum III (LeetCode 437) 🟦 Medium

Ссылка: https://leetcode.com/problems/path-sum-iii/

Условие: Найти количество путей с суммой = target. Путь может начинаться и заканчиваться в любом узле (но вниз).

Решение:

def pathSum(root, targetSum):
    count = [0]

    def dfs(node, current_sum):
        if not node:
            return

        current_sum += node.val

        if current_sum == targetSum:
            count[0] += 1

        dfs(node.left, current_sum)
        dfs(node.right, current_sum)

    def traverse(node):
        if not node:
            return

        dfs(node, 0)
        traverse(node.left)
        traverse(node.right)

    traverse(root)
    return count[0]

Объяснение:

traverse проходит каждый узел как потенциальное начало пути
dfs считает пути от этого узла вниз

Сложность: O(n²)

#6. Шпаргалка

Задача	Ключевая идея
Clone Graph	Словарь old → new
Course Schedule	3 состояния для цикла
Course Schedule II	Topological sort DFS
All Paths	Backtrack с path.pop()
Path Sum III	Двойной DFS

#7. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли backtrack

# ❌ Неправильно
path.append(neighbor)
dfs(neighbor, path)
# Забыли path.pop()!

# ✅ Правильно
path.append(neighbor)
dfs(neighbor, path)
path.pop()

#❌ Ошибка 2: Неправильная копия пути

# ❌ Неправильно
result.append(path)  # Ссылка!

# ✅ Правильно
result.append(path[:])  # Копия

#8. Заключение

DFS: Задачи на графы — обход графов с отслеживанием состояния.

Ключевые приёмы:

Clone Graph: словарь old_to_new
Course Schedule: 3 состояния (0, 1, 2)
All Paths: backtrack с path.pop()

Задача

Ключевая идея

Clone Graph

Словарь old → new

Course Schedule

3 состояния для цикла

Course Schedule II

Topological sort DFS

All Paths

Backtrack с path.pop()

Path Sum III

Двойной DFS

DFS: Графы