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

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

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

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

Контент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Обираємо стартову вершину s (якщо граф незв'язний - запускаємо з кожної невідвіданої вершини).
2. Позначаємо s як відвідану, виконуємо потрібну логіку (наприклад, записуємо в порядок обходу - preorder).
3. Проходимо по кожному сусіду v вершини s; якщо v не відвіданий - рекурсивно/через стек запускаємо DFS(v).
4. Після обробки всіх сусідів можна виконати пост-логіку (наприклад, записати в 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, дозволяє знаходити цикли, компоненти, будувати топологічний порядок і слугує основою для багатьох інших алгоритмів.

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

Для рев’юера

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

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