Що робить стек у DFS на графах?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Стек у DFS зберігає поточний шлях і стан вершин, у які ми зайшли, але ще не дослідили всіх сусідів. Завдяки принципу LIFO стек забезпечує заглиблення й бектрекінг: щойно у вершини закінчуються невідвідані сусіди, вона знімається зі стека, і алгоритм повертається до попередньої вершини. У рекурсивному варіанті роль цього стека виконує стек викликів.

Детальна відповідь

Навіщо потрібен стек у DFS

Керує порядком обходу (LIFO): останнім додали - першим обійшли, тому алгоритм заглиблюється.
Зберігає контекст вершини: саму вершину і, за потреби, індекс наступного сусіда, якого потрібно обробити.
Забезпечує бектрекінг: коли в поточної вершини більше немає невідвіданих сусідів, ми «виходимо» з неї і повертаємося до батька.
Дозволяє писати нерекурсивний DFS (важливо для великих графів, щоб уникнути переповнення стека викликів).

Що саме лежить у стеку

Простий варіант: сама вершина. Підходить, якщо нам потрібен лише порядок «входу» у вершини.
Розширений варіант (кадр/фрейм): { v, i } - вершина v та індекс наступного сусіда i. Це імітує рекурсію і дозволяє обробляти події «вхід/вихід».
Додатково іноді кладуть батька, час входу/виходу, колір вершини тощо, якщо задача цього вимагає.

Ітеративний DFS зі стеком (JS)

Простий обхід: позначаємо вершину відвіданою при додаванні в стек, щоб не класти дублікати.

function dfsIterative(adj, start) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const order = [];
  const stack = [start];
  visited[start] = true; // позначаємо під час push

  while (stack.length) {
    const v = stack.pop();
    order.push(v); // подія входу у вершину

    // Щоб порядок був стабільним зліва направо, пушимо сусідів у зворотному порядку
    for (let i = adj[v].length - 1; i >= 0; i--) {
      const u = adj[v][i];
      if (!visited[u]) {
        visited[u] = true;
        stack.push(u);
      }
    }
  }

  return order;
}

// Приклад
const adj = [
  [1, 2], // 0
  [3],    // 1
  [3],    // 2
  []      // 3
];
console.log(dfsIterative(adj, 0)); // [0, 1, 3, 2]

Обхід з подіями вхід/вихід (фрейми імітують стек викликів рекурсії):

function dfsWithEvents(adj, start, onEnter, onExit) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const stack = [{ v: start, i: 0, entered: false }];
  visited[start] = true;

  while (stack.length) {
    const top = stack[stack.length - 1];

    if (!top.entered) {
      if (onEnter) onEnter(top.v);
      top.entered = true; // подію входу оброблено
    }

    if (top.i < adj[top.v].length) {
      const u = adj[top.v][top.i++];
      if (!visited[u]) {
        visited[u] = true;
        stack.push({ v: u, i: 0, entered: false });
      }
    } else {
      if (onExit) onExit(top.v); // подія виходу
      stack.pop();
    }
  }
}

// Приклад використання
const enter = (v) => console.log('enter', v);
const exit = (v) => console.log('exit', v);
dfsWithEvents([[1,2],[3],[3],[]], 0, enter, exit);

Рекурсивний DFS: стек викликів робить те саме

function dfsRecursive(adj, start) {
  const n = adj.length;
  const visited = new Array(n).fill(false);
  const order = [];

  function rec(v) {
    visited[v] = true;           // аналог: push кадру
    order.push(v);               // подія входу
    for (const u of adj[v]) {
      if (!visited[u]) rec(u);
    }
    // тут подія виходу (перед поверненням)
  }

  rec(start);
  return order;
}

Складність і практичні деталі

Час: O(V + E) - кожну вершину і ребро розглядаємо обмежену кількість разів.
Пам'ять: O(V) - глибина стека в найгіршому випадку дорівнює довжині шляху.
Порядок сусідів впливає на порядок обходу. Щоб зберігати детермінованість, найчастіше сусідів сортують і пушать у зворотному порядку.
У неорієнтованому графі достатньо перевіряти visited; зберігати parent потрібно, якщо ви відрізняєте дерево від зворотних ребер (наприклад, для пошуку циклів).

Часті помилки на співбесіді

Позначати вершину відвіданою лише при pop, а не при push - призводить до множинних копій вершини в стеку.
Забувати знімати вершину зі стека після обробки всіх сусідів у варіанті з фреймами.
Не ініціалізувати visited заново між запусками DFS для різних компонент графа.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.