Графы и парадигмы: DFS, BFS, Dijkstra, DP, Backtracking, Sliding Window

Это второй урок алгоритмической под-серии. Урок 09 положил Big-O, структуры и базовые паттерны: бинарный поиск, хеш-мап, два указателя. Сегодня берём ту же оптику и применяем её к графам и к четырём парадигмам, на которых строится почти весь современный backend и инструменты.

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

Сцена · почему графы не для интервью, а для работы

Зайди в любой Node-проект. Откроется node_modules с десятком тысяч пакетов, и каждый пакет ссылается на другие. Это граф. Запусти pnpm ls --depth=2, и pnpm нарисует тебе подграф зависимостей. Сделай миграцию базы, и Drizzle построит граф зависимостей миграций (одна ждёт другую). Подключи roadmap или DAG в Airflow, и каждая задача станет узлом, а каждое “после” станет ребром.

Графы это не задача из учебника, а способ описать “что от чего зависит”. Если тебе понятен граф, тебе понятна половина проекта Node, в котором ты работаешь. Сегодня кладём фундамент: три представления, два обхода, три алгоритма путей. Дальше парадигмы, на которых решается всё остальное.

Карта урока · что заберёшь домой через 240 минут

Через четыре часа у тебя в голове будет:

• Графы и обходы. Adjacency list, matrix, edge list. DFS, BFS, Dijkstra. Bellman-Ford прозой, без виджета. Floyd-Warshall и A* упоминанием.
• Парадигмы. Greedy и его границы, Divide and Conquer, Dynamic Programming (top-down мемо и bottom-up табуляция), Backtracking (N-Queens и Permutations), Sliding Window (fixed и dynamic).
• Coin Change в четырёх версиях. Главный пример урока. На нём же и показываем, чем парадигмы различаются, не на словах.
• Финал. Чек-лист пятнадцати NeetCode-паттернов, четыре пункта ДЗ и мост на урок 11 про production-структуры.

Структура та же, что и в уроке 09: сцена, идея словами, виджет, упражнения, “что взять с собой”.

Раздел 1 · Утренний ритуал и топологическая сортировка

Сцена

“Встал, надел носки, надел ботинки, надел куртку, вышел из дома”. Если переставить шаги, ритуал ломается. Не потому что носки и ботинки нельзя поменять между собой (можно), а потому что ботинки требуют, чтобы носки уже были надеты. Это направленный ациклический граф: узлы это шаги, рёбра это “сначала вот это, потом вон то”.

Топологическая сортировка выдаёт такой ритуал в виде списка. У тебя на руках узлы и стрелки, на выходе линейная последовательность, в которой все стрелки направлены вперёд.

Идея словами

Граф можно хранить тремя способами, и выбор зависит от того, что у тебя часто:

1. Adjacency list. Для каждого узла список его соседей. Память O(V + E). Перебор соседей за O(deg(v)). Стандарт для разреженных графов.
2. Adjacency matrix. V × V таблица единиц и нулей (или весов). Память O(V²). Проверка ребра u-v за O(1). Хороша для плотных графов.
3. Edge list. Плоский список пар (u, v). Память O(E). Перебор соседей конкретного узла O(E). Используется в алгоритмах, которые ходят по рёбрам, а не по узлам (Bellman-Ford, Kruskal).

Топосорт по DAG делается двумя способами. Первый, через DFS: запусти DFS, и на выходе post-order развернутый назад это и есть топологический порядок. Второй, алгоритм Кана: считаем in-degree каждого узла, кладём в очередь все узлы с in_degree == 0, по очереди выгружаем и удаляем их рёбра. Если в конце очередь пуста, а узлы остались, в графе цикл.

A	[B, C]
B	[A, D]
C	[A, D, E]
D	[B, C, E, F]
E	[C, D, F]
F	[D, E]

	A	B	C	D	E	F
A	0	1	1	0	0	0
B	1	0	0	1	0	0
C	1	0	0	1	1	0
D	0	1	1	0	1	1
E	0	0	1	1	0	1
F	0	0	0	1	1	0

• (A, B)
• (A, C)
• (B, D)
• (C, D)
• (C, E)
• (D, E)
• (D, F)
• (E, F)

listΣ deg(v) = 2E = 16matrixV² = 36edge2E = 16

На разреженных графах (рёбер мало) list и edge почти равны и сильно дешевле matrix. На плотных (E близко к V²) matrix выгоднее и даёт O(1) на проверку есть ли ребро u-v. В nginx и pnpm графе зависимостей рёбер меньше, чем `V²`, поэтому в реальном коде ты увидишь именно adjacency list.

Упражнения

Что взять с собой

• Adjacency list это вариант по умолчанию. Adjacency matrix используют, когда граф плотный или когда нужны быстрые “есть ли ребро u-v”.
• Топосорт нужен везде, где есть зависимости: миграции, билды, npm install, очереди задач. Если граф не DAG (есть цикл), топосорт не существует, и нужно искать цикл (DFS с цветами или Tarjan).
• Граф у тебя уже есть в проекте: pnpm ls, миграции Drizzle, импорты ESM. Прокачаешь интуицию на них быстрее, чем на учебных задачах.

Раздел 2 · Лабиринт, DFS и BFS

Сцена

Ты в лабиринте. Хочешь выйти. Два разных стиля поведения:

1. Идти как можно глубже по одной ветке, пока не упрёшься в стену или тупик. Тогда вернуться к последней развилке и попробовать другую ветку. Это DFS.
2. Идти волной от старта: сначала все клетки на расстоянии 1, потом все на расстоянии 2, и так далее. Это BFS.

DFS использует стек, потому что нужно помнить “куда возвращаться”. BFS использует очередь, потому что нужно посещать в порядке “ранее добавленных”. На взвешенном графе ни DFS, ни BFS не дают кратчайших путей; на невзвешенном BFS даёт.

Идея словами

Псевдокод DFS итеративный:

1. Возьми стек, положи в него старт.
2. Пока стек не пуст: вытащи вершину сверху, отметь как посещённую, положи в стек её непосещённых соседей.

BFS отличается ровно одной строкой: вместо стека очередь, и “непосещённых соседей” мы помечаем как посещённых ещё в момент добавления (иначе один узел может попасть в очередь несколько раз).

Виджет ниже даёт оба обхода и Dijkstra на одном графе. Сначала переключись на dfs, потом на bfs. Сравни форму волны: DFS уходит в длину, BFS растекается.

Упражнения

Что взять с собой

• DFS и BFS отличаются одной структурой данных. Запомни: стек значит “глубже”, очередь значит “шире”.
• На невзвешенном графе BFS даёт кратчайший путь от старта. Это бесплатная фишка, не упускай её.
• DFS вкусен в задачах “обойди компонент целиком”, “найди цикл”, “топосортируй”. BFS вкусен в задачах “минимальное число шагов”.

Раздел 3 · Обмен пианино и Dijkstra

Сцена

У Бхаргавы в “Грокаем алгоритмы” есть классический пример: ты обмениваешь ноты пианино на пластинку, потом на гитару, потом на барабан. У каждого обмена есть стоимость. Найти самую дешёвую цепочку обменов это алгоритм Дейкстры.

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

Идея словами

Алгоритм:

1. dist[start] = 0, остальные Infinity. Положи (0, start) в priority queue.
2. Пока PQ не пуст: вытащи узел с минимальным dist. Если он уже посещён, пропусти. Иначе пометь как посещённый, и для каждого соседа v: если dist[node] + weight(node, v) < dist[v], обнови dist[v] и положи (dist[v], v) в PQ.

Главное правило: посещённый узел больше не пересматривается. Это и есть точка слома при отрицательных весах, потому что отрицательное ребро могло бы обнулить уже найденное расстояние, но Dijkstra про это не знает и проходит мимо.

Переключи виджет выше на dijkstra. Заметь два новых элемента: цифры под узлами это текущие dist, и панель PQ слева сортирует фронтьер по расстоянию. Floyd-Warshall (все пары кратчайших путей за O(V³)) и A* (Dijkstra плюс эвристика, нужен в поиске пути на сетке) одной выноской: они полезны, но в этом уроке не разбираем.

Упражнения

Что взять с собой

• Dijkstra даёт кратчайший путь от одного узла до всех остальных за O((V + E) log V) с binary heap.
• Если все веса равны 1, Dijkstra превращается в BFS. BFS быстрее, поэтому на невзвешенном графе всегда BFS, не Dijkstra.
• На отрицательных весах не Dijkstra. Дальше Bellman-Ford.