Clone Graph, Course Schedule, All Paths.
Обход графов с помощью DFS. Клонирование, цикл, топологическая сортировка.
Условие: Создать глубокую копию графа.
Решение:
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 хранит соответствие оригинал → копияСложность: O(n)
Условие: Можно ли пройти все курсы, заданы ли пререквизиты (граф зависимостей)?
Решение:
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Объяснение:
Сложность: O(V + E)
Условие: Верните порядок прохождения курсов.
Решение (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)
Условие: Дан ациклический граф. Найти все пути от 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Объяснение:
Сложность: O(2^n × n)
Условие: Найти количество путей с суммой = 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²)
| Задача | Ключевая идея |
|---|---|
| Clone Graph | Словарь old → new |
| Course Schedule | 3 состояния для цикла |
| Course Schedule II | Topological sort DFS |
| All Paths | Backtrack с path.pop() |
| Path Sum III | Двойной DFS |
# ❌ Неправильно
path.append(neighbor)
dfs(neighbor, path)
# Забыли path.pop()!
# ✅ Правильно
path.append(neighbor)
dfs(neighbor, path)
path.pop()# ❌ Неправильно
result.append(path) # Ссылка!
# ✅ Правильно
result.append(path[:]) # КопияDFS: Задачи на графы — обход графов с отслеживанием состояния.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.