Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що робить стек у DFS на графах?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

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

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

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

```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]
```

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

```js
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: стек викликів робить те саме

```js
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 для різних компонент графа.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати617 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.