Алгоритмы с нуля
Поиск в глубину (DFS)
Ты знаешь как обходить дерево: выбери корень, посети его детей, потом их детей, в некотором порядке. Поиск в глубину (DFS) расширяет это на графы. Но есть критическое отличие: граф может иметь циклы. В дереве, есть ровно один путь между двумя узлами — раз ты посетил узел, ты никогда его не видишь снова. В графе с циклами (A → B → A), ты мог бы зацикливаться навсегда, посещая одни и те же вершины снова и снова. Решение простое и критичное: отслеживай какие вершины ты уже посетил и никогда не посещай их дважды. Этот урок учит DFS в его двух формах — рекурсивный (естественный и элегантный) и итеративный с явным стеком (яснее о порядке исследования) — и показывает почему множество посещённых вершин критично.
После этого урока ты можешь написать DFS как рекурсивную функцию и как итеративную функцию с явным стеком. Ты понимаешь почему множество посещённых вершин необходимо для графов (чтобы предотвратить бесконечные циклы на циклических графах), хотя деревья его не требуют. Ты можешь трассировать DFS на конкретном графе со списком смежности и предсказать порядок в котором вершины посещаются. Ты понимаешь сложность DFS O(V+E) по времени и O(V) по памяти, и ты можешь определить когда DFS это инструмент для использования: исследование всех вершин достижимых из начальной вершины, или проверка связности. Следующий урок это поиск в ширину (BFS), что исследует слой за слоем вместо глубины.
Что это поиск в глубину?
Поиск в глубину (DFS) это обход графа, что исследует насколько возможно по каждому ребру перед отходом назад. Он посещает каждую вершину достижимую от начальной вершины, в порядке поиска в глубину.
Почему DFS это другое от обхода дерева
В дереве, раз ты посетил узел, нет другого пути к нему — невозможно посетить его дважды. В графе с циклами, одна вершина может быть достижима через множественные пути. Если ты не отслеживаешь посещённые вершины, ты будешь зацикливаться навсегда:
Дерево (нет циклов): Граф (имеет цикл):
1 0
/ \ /|\
2 3 1 2 3
|/
1 ← цикл!В дереве, ты посещаешь 1, потом 2 (раз), потом 3 (раз). Готово.
В графе, начиная от 0, ты мог бы идти 0 → 1 → 1 → 1 … (бесконечный цикл если ты не отмечаешь 1 как посещённо).
Исправление: поддерживай множество посещённых вершин — множество (или булев массив) записывающее какие вершины ты уже посетил. Перед посещением вершины, проверь есть ли она в множестве посещённых. Если да, пропусти её. Если нет, отметь её посещённо и исследуй её соседей.
Рекурсивный DFS: простой и естественный
Рекурсивный подход зеркалит обход дерева:
- Отметь текущую вершину как посещённо.
- Для каждого соседа текущей вершины:
- Если сосед не посещён, рекурсивно посети его.
Это всё. Рекурсивный вызов стек естественно управляет отходом назад. Когда рекурсивный вызов возвращается, ты автоматически отходишь назад чтобы исследовать других соседей.
Итеративный DFS: явный стек
Рекурсивная версия это элегантна но полагается на стек вызовов функции. Итеративная версия делает стек явным: добавь начальную вершину на стек, потом:
- Пока стек не пуст:
- Извлеки вершину.
- Если она не посещена, отметь её посещённо и добавь всех её непосещённых соседей на стек.
Порядок в котором ты добавляешь соседей влияет на порядок в котором они исследуются (LIFO из стека).
Пример графа
Давайте используем простой ориентированный граф с 4 вершинами и 5 рёбрами:
Список смежности:
0: [1, 2]
1: [3]
2: [3]
3: [2]
Визуально:
0 → 1
↓ ↓
2 → 3
↑ ↓
+---+Вершина 3 имеет ребро назад к 2 (цикл). Начиная от вершины 0, DFS посетит 0, потом 1 или 2 (в зависимости от порядка соседей), потом 3, потом назад к 2 если не ещё посещена, или пропусти её если уже посещена.
Рекурсивный DFS на примере
посещённо = {}
Начни с 0.
- Отметь 0 посещённо.
- Сосед 1: не посещён, рекурсируй.
- Отметь 1 посещённо.
- Сосед 3: не посещён, рекурсируй.
- Отметь 3 посещённо.
- Сосед 2: не посещён, рекурсируй.
- Отметь 2 посещённо.
- Сосед 3: уже посещён, пропусти.
- Готово с 2.
- Готово с 3.
- Готово с 1.
- Сосед 2: уже посещён, пропусти.
- Готово с 0.
Финальный порядок посещения: 0 → 1 → 3 → 2.Рекурсивный DFS
1
function dfsRecursive(vertex, adj, visited) {
2
// Отметь эту вершину как посещённо
3
visited.add(vertex);
4
5
// Для каждого соседа этой вершины
6
for (const neighbor of adj[vertex]) {
7
// Если сосед не посещён, рекурсируй
8
if (!visited.has(neighbor)) {
9
dfsRecursive(neighbor, adj, visited);
10
}
11
}
12
}
13
14
// Чтобы начать DFS из вершины:
15
const visited = new Set();
16
dfsRecursive(startVertex, adj, visited);
- L1 Берёт вершину, список смежности и множество посещённых вершин.
- L2 Отметь эту вершину посещённо (перед исследованием соседей, не после).
- L5 Итерируй всех соседей текущей вершины.
- L7 Рекурсируй только в непосещённых соседей.
- L11 Вызови с начальной вершиной и пустым множеством посещённых.
Итеративный DFS с явным стеком
1
function dfsIterative(startVertex, adj) {
2
const visited = new Set();
3
const stack = [startVertex];
4
5
while (stack.length > 0) {
6
const vertex = stack.pop();
7
8
// Только процессируй если ещё не посещена
9
if (!visited.has(vertex)) {
10
visited.add(vertex);
11
12
// Добавь непосещённых соседей на стек (в обратном порядке для согласованного исследования)
13
for (let i = adj[vertex].length - 1; i >= 0; i--) {
14
const neighbor = adj[vertex][i];
15
if (!visited.has(neighbor)) {
16
stack.push(neighbor);
17
}
18
}
19
}
20
}
21
22
return visited;
23
}
- L1 Итеративная версия используя явный стек.
- L2 Инициализируй множество посещённых вершин.
- L3 Инициализируй стек с начальной вершиной.
- L5 Пока стек не пуст, извлеки вершину.
- L9 Проверь есть ли эта вершина уже посещена.
- L10 Отметь её посещённо.
- L13 Добавь непосещённых соседей. Мы итерируем в обратном порядке чтобы сохранить один и тот же порядок исследования как рекурсивный DFS.
- L20 Верни множество всех посещённых вершин.
Запуск DFS на графе
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
visited = new Set();
3
dfsRecursive(0, adj, visited);
1
adj = { 0: [1, 2], 1: [3], 2: [3], 3: [2] };
2
stack = [0];
3
visited = new Set();
4
dfsIterative(0, adj);
Сложность по времени: O(V + E)
DFS посещает каждую вершину раз (V вершин) и каждое ребро дважды (раз с каждого конца). На самом деле, каждое ребро исследуется раз в направлении списка смежности. Для ориентированного графа, каждое ребро исследуется ровно раз когда мы итерируем соседей его исходной вершины. Итоговая работа: V посещений + E итераций рёбер = O(V + E).
Пример: Граф с 5 вершинами и 7 рёбрами использует O(5 + 7) = O(12) операций — независимо от того редкий ли граф или плотный.
Сложность по памяти: O(V)
Множество посещённых вершин хранит до V записей (одна за вершину): O(V).
Стек рекурсии (в рекурсивном DFS) может быть такой же глубокий как V в наихудшем случае (длинная цепь: 0 → 1 → 2 → … → V-1): O(V).
Явный стек (в итеративном DFS) может удерживать до V вершин одновременно (в графе с высокой ветвлением): O(V).
Итоговая память: O(V).
Почему множество посещённых вершин критично
Без множества посещённых вершин, DFS на циклическом графе будет зацикливаться навсегда:
Пример: 0 → 1 → 0 (2-цикл)
Без множества посещённых вершин:
Посети 0, иди к 1.
Посети 1, иди к 0.
Посети 0, иди к 1.
Посети 1, иди к 0.
... (бесконечно)
С множеством посещённых {0, 1}:
Посети 0, отметь посещённо.
Иди к 1 (не посещена).
Посети 1, отметь посещённо.
Иди к 0 (уже посещена), пропусти.
Готово.Деревья не имеют циклов, так обход дерева не строго требует множество посещённых вершин (ты не переучитаешь родителя). Но отмечание вершин при посещении их это всё ещё хорошая практика и делает код яснее.
В графе с циклом (например, 0 → 1 → 0), что происходит если ты запустишь DFS без множества посещённых вершин?
Какая сложность по времени DFS на графе с V вершинами и E рёбрами?
В рекурсивном DFS, какая структура данных используется имплицитно чтобы управлять отходом назад?
Какая сложность по памяти DFS, включая множество посещённых вершин и стек (рекурсивный или итеративный)?
Если ты хочешь DFS исследовать соседей в одном и том же порядке для обеих рекурсивной и итеративной версий, как ты должен добавлять соседей на стек в итеративной версии?
Граф имеет 6 вершин и 9 рёбер. Какая примерная сложность по времени O(V + E) в терминах итогового числа посещений вершин и исследований рёбер?
lesson.inset.undefined
Почему DFS и не BFS? Оба DFS и BFS исследуют все достижимые вершины и имеют одну и ту же сложность по времени O(V + E). DFS это проще кодировать (особенно рекурсивно) и использует меньше памяти когда граф это очень глубокий и узкий (длинная цепь). BFS это лучше когда ты нужна кратчайший путь (количество рёбер) или хочешь исследовать слой-за-слоем. За теперь, DFS это твой инструмент для исследования всех достижимых вершин и обнаружения циклов.
lesson.inset.undefined
Забывание множество посещённых вершин. Это соблазнительно пропустить множество посещённых вершин на малых примерах или когда ты думаешь “граф не имеет циклов.” Но циклы это легко пропустить, и даже ациклические графы могут иметь множественные пути к одной вершине (DAG — ориентированный ациклический граф). Всегда включай множество посещённых вершин. Это дешево (O(V) память) и спасает тебя от бесконечных циклов.
lesson.inset.undefined
Несвязные графы. Если граф имеет множественные несвязные компоненты, DFS из одной вершины только посетит вершины достижимые от этой вершины. Чтобы посетить все вершины в несвязном графе, ты должен начать новый DFS из непосещённой вершины. Это основание алгоритма связные-компоненты (идущего в позднем уроке).
lesson.inset.undefined
DFS для достижимости. DFS отвечает вопрос: “Начиная от вершины A, какие вершины я могу достичь?” Если ты хочешь знать есть ли путь от A к B, запусти DFS от A и проверь есть ли B в множестве посещённых. Если да, есть путь. Если нет, нет пути.
Объясни что такое DFS, почему множество посещённых вершин необходимо для графов (но не деревьев), и опиши сложность по времени и памяти.
Поиск в глубину (DFS) исследует граф идя насколько возможно по каждому ребру перед отходом назад. Это использует множество посещённых вершин чтобы предотвратить переучитывание вершин — критично для графов с циклами, в отличие деревьев.
Две реализации:
- Рекурсивный DFS: Естественный и простой; стек вызовов управляет отходом назад.
- Итеративный DFS: Используёт явный стек; яснее о состоянии.
Оба посещают каждую вершину раз и исследуют каждое ребро раз. Время: O(V + E). Память: O(V) для множество посещённых вершин и стека.
Используй DFS чтобы исследовать все достижимые вершины, обнаружить связность, или проверить пути. Следующий урок: поиск в ширину (BFS) — исследуй слой за слоем вместо глубины.