Що робить алгоритм DFS на графах (Depth-First Search)?

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

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

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

Розгорнута відповідь

Що робить DFS на графах

Обходить граф углиб: обирає вершину, йде по ребру вглиб, поки можливо, потім відкочується назад (backtracking).
Позначає вершини як відвідані, щоб не зациклитися і не обробляти їх повторно.
Формує різні порядки обходу: preorder (вхід), postorder (вихід), які корисні, наприклад, для топологічного сортування.
Обробляє як напрямлені, так і ненапрямлені графи; підходить і для дерев (окремий випадок графа).

Складність

Час: O(V + E), де V - кількість вершин, E - кількість ребер (кожна вершина й ребро обробляються не більше одного разу).
Пам'ять: O(V) для зберігання міток відвідування та стека викликів (рекурсія) або власного стека (ітеративно).

Де застосовується

Перевірка зв'язності графа / підрахунок компонент зв'язності
Знаходження шляхів і предків (для відновлення маршрутів)
Виявлення циклів (і в напрямлених, і в ненапрямлених графах)
Топологічне сортування в DAG (напрямлений ациклічний граф)
Пошук точок з'єднання і мостів, компонент сильної зв'язності (з модифікаціями)

Як працює (покроково)

Обираємо стартову вершину s (якщо граф незв'язний - запускаємо з кожної невідвіданої вершини).
Позначаємо s як відвідану, виконуємо потрібну логіку (наприклад, записуємо в порядок обходу - preorder).
Проходимо по кожному сусіду v вершини s; якщо v не відвіданий - рекурсивно/через стек запускаємо DFS(v).
Після обробки всіх сусідів можна виконати пост-логіку (наприклад, записати в postorder).

Реалізація: рекурсивна (JavaScript)

javascript

function dfsRecursive(graph, start, visited = new Set(), preorder = [], postorder = []) {
  visited.add(start);
  preorder.push(start); // момент входу у вершину
  for (const nei of graph[start] || []) {
    if (!visited.has(nei)) dfsRecursive(graph, nei, visited, preorder, postorder);
  }
  postorder.push(start); // момент виходу з вершини
  return { visited, preorder, postorder };
}

// Приклад: орієнтований граф
// A: B, C; B: D, E; C: F; E: F
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

const { preorder, postorder } = dfsRecursive(graph, 'A');
console.log('preorder:', preorder.join(' -> '));
console.log('postorder:', postorder.join(' -> '));
// Можливий вивід (залежить від порядку сусідів):
// preorder: A -> B -> D -> E -> F -> C
// postorder: D -> F -> E -> B -> C -> A

Реалізація: ітеративна зі стеком (JavaScript)

javascript

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    order.push(v); // аналог preorder
    // Щоб порядок був ближчим до рекурсивного, додаємо сусідів у стек у зворотному порядку
    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 order;
}

const order = dfsIterative(graph, 'A');
console.log('iterative order:', order.join(' -> '));

Пре- і постномери. Топологічне сортування

Преномер (pre) фіксує момент входу у вершину, постномер (post) - момент виходу. У DAG топологічний порядок можна отримати, записавши вершини в postorder і розвернувши список.

javascript

function topoSortDAG(graph) {
  const visited = new Set();
  const post = [];

  function dfs(v) {
    visited.add(v);
    for (const nei of graph[v] || []) if (!visited.has(nei)) dfs(nei);
    post.push(v);
  }

  for (const v of Object.keys(graph)) if (!visited.has(v)) dfs(v);
  return post.reverse(); // топологічний порядок
}

console.log('topo:', topoSortDAG(graph).join(' -> '));

Виявлення циклів

Ідея: в орієнтованому графі використовуємо розфарбування вершин (0 - не відвідана, 1 - у стеку рекурсії, 2 - оброблена). Ребро в сіру вершину (1) - цикл. У неорієнтованому графі уникаємо «зворотного ребра до батька», пам'ятаючи parent.

javascript

// Цикл в орієнтованому графі
function hasCycleDirected(graph) {
  const color = new Map(); // 0: white, 1: gray, 2: black
  for (const v of Object.keys(graph)) color.set(v, 0);

  function dfs(u) {
    color.set(u, 1);
    for (const v of graph[u] || []) {
      const c = color.get(v) ?? 0;
      if (c === 1) return true; // back-edge => цикл
      if (c === 0 && dfs(v)) return true;
    }
    color.set(u, 2);
    return false;
  }

  for (const v of Object.keys(graph)) if (color.get(v) === 0 && dfs(v)) return true;
  return false;
}

// Цикл у неорієнтованому графі
function hasCycleUndirected(graph) {
  const visited = new Set();
  function dfs(u, parent = null) {
    visited.add(u);
    for (const v of graph[u] || []) {
      if (!visited.has(v)) {
        if (dfs(v, u)) return true;
      } else if (v !== parent) {
        return true; // знайшли зворотне ребро не до батька => цикл
      }
    }
    return false;
  }
  for (const v of Object.keys(graph)) if (!visited.has(v) && dfs(v, null)) return true;
  return false;
}

Особливості та нюанси

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

Підсумок

DFS - базовий інструмент роботи з графами: швидкий, просто реалізується (рекурсивно або через стек), дає доступ до preorder/postorder, дозволяє знаходити цикли, компоненти, будувати топологічний порядок і слугує основою для багатьох інших алгоритмів.

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

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

Premium

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