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

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

Допрацюйте відповідь до «Що таке Depth-first search (пошук у глибину)?». Ваші зміни проходять модерацію перед публікацією.

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

Контент

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

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

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

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

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

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

Depth-first search (пошук у глибину, DFS) - це алгоритм обходу графів і дерев, який іде якомога глибше в одному напрямку, поки є невідвідані вершини, потім відкочується (backtracking) і продовжує з найближчої альтернативної гілки. Використовує стек: або неявний (рекурсія), або явний. Складність за часом O(V + E), за пам'яттю O(V) з урахуванням стека викликів.

## Детальне пояснення

### Ідея алгоритму

- Починаємо зі стартової вершини s, позначаємо її відвіданою (visited).
- Переходимо до першого невідвіданого сусіда і повторюємо процес, заглиблюючись до упору.
- Якщо в поточної вершини немає невідвіданих сусідів - відкат (backtracking) до попередньої вершини і пошук альтернативної гілки.
- Повторюємо, поки стек порожній і всі досяжні вершини оброблені.

### Рекурсивний vs ітеративний варіант

- Рекурсивний: простіше записати і читати; стек викликів виконує роль стека обходу.
- Ітеративний: явний стек (масив/структура Stack). Краще контролює глибину і уникає переповнення стека викликів.
- Порядок відвідування залежить від порядку сусідів і того, як ви додаєте їх у стек.

### Порядки обходу дерев

- Preorder (NLR): спочатку вузол, потім ліве піддерево, потім праве.
- Inorder (LNR): ліве, вузол, праве (важливо для BST - дає відсортований порядок).
- Postorder (LRN): ліве, праве, вузол (використовується для видалення/звільнення ресурсів).

### Складність

- Час: O(V + E), де V - кількість вершин, E - кількість ребер.
- Пам'ять: O(V) на visited + O(H) глибина стека (H ≤ V). У гіршому випадку O(V).

### Де застосовують

- Перевірка досяжності і пошук шляху між вершинами.
- Знаходження компонент зв'язності (у неорієнтованих графах).
- Детекція циклів (особливо в орієнтованих графах - через кольори/стек рекурсії).
- Топологічне сортування (DAG) - використовується постпорядок.
- Задачі на backtracking: генерація комбінацій/перестановок, Судоку, N-Queens.
- Обхід по сітці/лабіринту (наприклад, підрахунок «островів»).

### Підводні камені і поради

- Не забувайте visited: без нього потрапите в нескінченний цикл за наявності циклів.
- Глибока рекурсія може переповнити стек: обирайте ітеративний варіант або збільшуйте ліміт (якщо можливо).
- Порядок сусідів впливає на конкретний порядок відвідування, але не на коректність результатів класів задач (наприклад, досяжність/компоненти).
- Для обходу всіх вершин у незв'язному графі запускайте DFS з кожної невідвіданої вершини.

### Як відповісти на співбесіді

- Дайте визначення: «обходить якомога глибше, потім відкочується; використовує стек/рекурсію».
- Назвіть складності: час O(V+E), пам'ять O(V).
- Згадайте visited і обробку циклів, рекурсивний і ітеративний варіанти.
- Наведіть 1-2 застосування: топологічне сортування, перевірка досяжності, острови на сітці.

## Приклади коду

### DFS на графі (рекурсивно)

```javascript
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: [],
};

dfsRecursive(graph, 'A', v => console.log('visit', v));
```

### DFS на графі (ітеративно зі стеком)

```javascript
function dfsIterative(graph, start, visit = () => {}) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    visit(v);
    const neighbors = graph[v] || [];
    // Щоб порядок збігався з рекурсією, додаємо сусідів у стек у зворотному порядку
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const nei = neighbors[i];
      if (!visited.has(nei)) stack.push(nei);
    }
  }
  return visited;
}

// Приклад використання:
// dfsIterative(graph, 'A', v => console.log('visit', v));
```

### Пошук шляху між двома вершинами (DFS)

```javascript
function dfsPath(graph, start, target) {
  const visited = new Set();
  const parent = new Map();
  let found = false;

dfs(start);
  if (!found) return null;
  const path = [];
  for (let v = target; v != null; v = parent.get(v)) path.push(v);
  path.reverse();
  return path;
}

console.log(dfsPath(graph, 'A', 'F')); // Наприклад: [ 'A', 'B', 'E', 'F' ]
```

### DFS на дереві: preorder / inorder / postorder

```javascript
class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(1,
  new Node(2, new Node(4), new Node(5)),
  new Node(3)
);

function preorder(node, visit) {
  if (!node) return;
  visit(node.val);
  preorder(node.left, visit);
  preorder(node.right, visit);
}

function inorder(node, visit) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.val);
  inorder(node.right, visit);
}

function postorder(node, visit) {
  if (!node) return;
  postorder(node.left, visit);
  postorder(node.right, visit);
  visit(node.val);
}

preorder(root, v => console.log('pre', v));   // 1,2,4,5,3
inorder(root, v => console.log('in', v));     // 4,2,5,1,3
postorder(root, v => console.log('post', v)); // 4,5,2,3,1
```

### DFS на матриці (підрахунок кількості «островів»)

```javascript
function numIslands(grid) {
  const m = grid.length;
  const n = grid[0]?.length || 0;
  const seen = Array.from({ length: m }, () => Array(n).fill(false));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

function dfs(r, c) {
    if (r < 0 || c < 0 || r >= m || c >= n) return;
    if (seen[r][c] || grid[r][c] !== '1') return;
    seen[r][c] = true;
    for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
  }

let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!seen[r][c] && grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

const grid = [
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','1','1'],
];
console.log(numIslands(grid)); // 3
```

### Детекція циклу і топологічне сортування (DAG)

```javascript
function hasCycleDirected(graph) {
  const color = new Map(); // 0=white,1=gray,2=black
  const nodes = Object.keys(graph);

function dfs(v) {
    color.set(v, 1);
    for (const nei of graph[v] || []) {
      const c = color.get(nei) || 0;
      if (c === 1) return true; // зворотне ребро => цикл
      if (c === 0 && dfs(nei)) return true;
    }
    color.set(v, 2);
    return false;
  }

for (const v of nodes) {
    if ((color.get(v) || 0) === 0 && dfs(v)) return true;
  }
  return false;
}

function topoSort(graph) {
  const visited = new Set();
  const order = [];

function dfs(v) {
    visited.add(v);
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) dfs(nei);
    }
    order.push(v); // постпорядок
  }

for (const v of Object.keys(graph)) {
    if (!visited.has(v)) dfs(v);
  }
  order.reverse();
  return order;
}

// Приклад:
const dag = {
  A: ['C'],
  B: ['C', 'D'],
  C: ['E'],
  D: ['F'],
  E: ['H', 'F'],
  F: ['G'],
  G: [],
  H: []
};

console.log('hasCycle', hasCycleDirected(dag)); // false
console.log('topo', topoSort(dag)); // один із коректних порядків
```

### Підсумок

DFS - простий і потужний базовий алгоритм. Він обходить граф/дерево, заглиблюючись до упору, спирається на стек (явний або рекурсивний), має лінійну складність O(V+E) і широко застосовується: від пошуку шляхів і компонент до топологічного сортування і задач backtracking. Ключові моменти: коректно ведіть visited і враховуйте глибину стека.

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

Для рев’юера

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

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