Пошук у глибину (DFS) і пошук в ширину (BFS)

Повне пояснення

Коротке пояснення

DFS (Depth‑First Search) просувається глибоко по графу, відвідуючи вершину і рекурсивно переходячи до її суміжних. BFS (Breadth‑First Search) розширює рівень за рівнем, використовуючи чергу, і таким чином знаходить найкоротший шлях у неважкості.

Аналогія

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

Коли застосовувати

• Потрібно знайти будь‑який шлях між двома вершинами.
• Граф не має ваг, а важливий лише порядок обходу.
• Потрібно перевірити зв’язність графа.
• Пошук у глибину підходить для задач, де потрібен повний список всіх шляхів.
• BFS використовується, коли треба знайти найкоротший шлях у неважкості.

Кроки алгоритму

1. Відкрити вершину, позначити її як відвідану.
2. Для DFS: рекурсивно або з стеком обробити кожну суміжну вершину, що ще не відвідана.
3. Для BFS: додати суміжні вершини до черги, позначити їх як відвідані.
4. Повторювати крок 2/3, доки не буде оброблено всі вершини.
5. Повернути список відвіданих вершин або шлях, якщо потрібен.

Візуальна інтуїція (текстова)

DFS:

A → B → D
    ↘ E
C → F

BFS:

Level 0: A
Level 1: B, C
Level 2: D, E, F

Складність

DFS і BFS мають O(V + E) час, де V – кількість вершин, E – ребер. Пам’ять: DFS рекурсивно потребує O(V) стеку, BFS – O(V) черги. У найгіршому випадку обидва обходять усі вершини і ребра.

Код (js)

// Граф представляється у вигляді об’єкта: ключ – вершина, значення – масив суміжних вершин
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

// ---------- DFS (рекурсивний) ----------
function dfs(start, visited = new Set(), order = []) {
  // 1. Позначаємо поточну вершину як відвідану
  visited.add(start);
  order.push(start); // 2. Додаємо до порядку обходу

  // 3. Рекурсивно обходимо суміжні вершини, що ще не відвідані
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, visited, order);
    }
  }

  return order; // 4. Повертаємо повний порядок обходу
}

// ---------- BFS (черговий) ----------
function bfs(start) {
  const visited = new Set(); // 1. Створюємо множину відвіданих
  const queue = [start];     // 2. Черга з початковою вершиною
  const order = [];          // 3. Порядок обходу

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift(); // 4. Витягуємо з черги
    order.push(vertex);           // 5. Додаємо до порядку

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // 6. Позначаємо як відвідану
        queue.push(neighbor);   // 7. Додаємо до черги
      }
    }
  }

  return order; // 8. Повертаємо порядок обходу
}

// ---------- Тестові приклади ----------
console.log(dfs('A')); // очікуваний результат: ['A', 'B', 'D', 'E', 'F', 'C']
console.log(bfs('A')); // очікуваний результат: ['A', 'B', 'C', 'D', 'E', 'F']

Типові помилки і поради

1. Не позначати вершину як відвідану перед рекурсивним викликом – це призведе до зациклення.
2. Використовувати глобальну змінну для visited у рекурсії – це зіпсує результати при кількох викликах.
3. Забувати очищати чергу у BFS – залишиться зайва пам’ять і неправильний порядок.
4. Не перевіряти, чи вершина існує у графі – це викличе помилку.
5. Використовувати стек замість черги у BFS – алгоритм перестане працювати як ширинний.

Перевір себе

1. Яка складність часу має DFS у найгіршому випадку?
2. Чому BFS гарантує знайти найкоротший шлях у неважкості?