Що таке Depth-first search (пошук у глибину)?

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

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

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: [],
};

function dfsRecursive(graph, start, visit = () => {}) {
  const visited = new Set();
  function dfs(v) {
    visited.add(v);
    visit(v);
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) dfs(nei);
    }
  }
  dfs(start);
  return visited; // множина відвіданих вершин
}

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;

  function dfs(v) {
    if (found) return;
    visited.add(v);
    if (v === target) { found = true; return; }
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) {
        parent.set(nei, v);
        dfs(nei);
      }
    }
  }

  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 і враховуйте глибину стека.

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

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

Premium

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