Паттерн: Обход в глубину

Признак в условии

• вложенная структура: дерево, вложенные объекты, матрица
• «обойти всё», «есть ли путь», «связные области»
• задача естественно разбивается на такую же задачу поменьше

Шаблон

function walk(node, state) {
  if (!node) return база;
  if (посещён(node)) return;
  пометить(node);
  for (const next of соседи(node)) walk(next, state);
}

Для матрицы проверку границ делают в начале функции, а не перед каждым вызовом:

const fill = (r, c) => {
  if (r < 0 || c < 0 || r >= rows || c >= cols) return;
  if (grid[r][c] !== искомое) return;
  grid[r][c] = помечено;
  fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1);
};

Ориентированный граф - три цвета

Двух состояний мало: нужно отличать «в текущем пути» (серый) от «обработан» (чёрный). Ребро в серую вершину - цикл.

Сложность

Время O(V + E), память O(глубины) на стек вызовов.

Частые ошибки

• нет защиты от повторного посещения - зацикливание на графе с циклами
• два состояния вместо трёх при поиске цикла: ромб ошибочно объявляется циклическим
• глубокая рекурсия переполняет стек - на больших данных нужен явный стек
• при проверке BST сравнивают только с непосредственным родителем

Мнемоника

«Вглубь до упора, потом назад»

Не путать с

• Обход в ширину - в глубину - когда нужен любой путь, все пути или структура (компоненты, циклы); в ширину - когда нужен кратчайший
• Перебор с возвратом - перебор с возвратом - это обход в глубину по дереву решений с отменой выбора; если отменять нечего, это просто обход

Задачи на этот паттерн

• глубина дерева
• плоский список узлов дерева
• число островов
• проверка двоичного дерева поиска
• зеркальное отражение дерева
• ближайший общий предок
• есть ли путь с суммой
• сериализация дерева
• цикл в ориентированном графе
• заливка области
• одинаковые ли деревья
• зеркальность дерева
• диаметр дерева
• число связных групп

Признак в условии

• «кратчайший путь» в невзвешенном графе
• «по уровням», «минимум шагов», «сколько ходов»
• вид дерева сбоку, обход по слоям

Шаблон

let level = [start];
const visited = new Set([start]);
let depth = 0;
while (level.length) {
  const next = [];
  for (const node of level) {
    if (цель(node)) return depth;
    for (const n of соседи(node)) {
      if (visited.has(n)) continue;
      visited.add(n);              // помечаем при ДОБАВЛЕНИИ
      next.push(n);
    }
  }
  level = next;
  depth++;
}

Топологическая сортировка (алгоритм Кана)

Очередь вершин с нулевой входящей степенью; снимая вершину, уменьшаем степень соседей. Если обработаны не все вершины - в графе цикл.

Сложность

Время O(V + E), память O(ширины уровня).

Частые ошибки

• пометка посещения при извлечении вместо добавления: вершина попадает в очередь многократно
• queue.shift() на больших очередях даёт O(n) на операцию - для миллионов элементов нужен индекс головы
• поуровневая обработка забыта там, где нужна глубина

Мнемоника

«Очередь, посетить один раз, слой за слоем»

Не путать с

• Обход в глубину - в ширину - только когда важна минимальность шагов. Иначе дешевле и короче в глубину
• Динамическое программирование - если граф - сетка и переходы только вперёд, кратчайший путь часто считается динамикой без очереди

Задачи на этот паттерн

• обход по уровням
• вид дерева справа
• обход графа в ширину
• топологическая сортировка
• обход зигзагом
• можно ли пройти все курсы
• распространение по слоям

Суть

Граф это вершины и рёбра. Деревья, сетки, зависимости пакетов, друзья в соцсети: всё графы. На собесе почти всегда хватает двух обходов: BFS (волнами) и DFS (вглубь).

Как распознать по условию

• «минимальное число шагов / ходов / превращений» в графе без весов → BFS;
• «сколько компонент, островов, групп» → DFS или BFS от каждой непосещённой;
• «есть ли путь», «есть ли цикл» → DFS;
• «порядок с зависимостями», «можно ли пройти все курсы» → топосортировка;
• сетка grid[r][c] → граф, где соседи это 4 (или 8) клетки.

Представление

// рёбра [[a, b], ...] → список смежности
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }

BFS

function bfs(adj, start) {
  const dist = new Array(adj.length).fill(-1);
  dist[start] = 0;
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const v = queue[head];
    for (const u of adj[v]) {
      if (dist[u] === -1) {        // пометка при добавлении
        dist[u] = dist[v] + 1;
        queue.push(u);
      }
    }
  }
  return dist;
}

DFS на сетке (итеративный)

function islands(grid) {
  const R = grid.length, C = grid[0].length;
  let count = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (grid[r][c] !== '1') continue;
    count++;
    const stack = [[r, c]];
    grid[r][c] = '0';
    while (stack.length) {
      const [y, x] = stack.pop();
      for (const [dy, dx] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const ny = y + dy, nx = x + dx;
        if (ny >= 0 && ny < R && nx >= 0 && nx < C && grid[ny][nx] === '1') {
          grid[ny][nx] = '0';
          stack.push([ny, nx]);
        }
      }
    }
  }
  return count;
}

Скажи интервьюеру, что меняешь входную сетку, или заведи visited.

Топосортировка (Кан)

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

Сложность

BFS, DFS, Кан: O(V + E) времени, O(V) памяти. Сетка: O(R · C).

Ловушки

• queue.shift() вместо индекса головы.
• Пометка посещённых при извлечении: дубликаты в очереди.
• Рекурсивный DFS на большой сетке: переполнение стека.
• Цикл в ориентированном графе через один visited: нужны три состояния.
• BFS на графе с весами: нужен Дейкстра.

Что спросят на собесе

• Чем BFS отличается от DFS, когда что?
• Посчитай острова в сетке.
• Почему BFS даёт кратчайший путь без весов?
• Можно ли пройти все курсы с зависимостями?
• Как хранить граф и почему не матрицей?