Поиск в ширину - BFS

В глубинном поиске (DFS) мы уделяли приоритет глубине. В поиске в ширину (breadth-first search - BFS) мы уделяем приоритет ширине. Напомним, что глубина узла — это его расстояние от корня. В DFS мы старались углубиться настолько, насколько это возможно, увеличивая глубину текущего узла, пока не достигали листа. Если вы выполнили DFS на большом дереве, глубина узлов, которые вы бы обошли, может выглядеть как: 0, 1, 2, 3, 4, 5, 6, ...

В BFS мы обходим все узлы на заданной глубине перед переходом к следующей. Таким образом, если вы выполните BFS на большом полном бинарном дереве, глубина узлов, которые вы бы обошли, будет выглядеть как: 0, 1, 1, 2, 2, 2, 2, 3, 3, ...

"Полное" бинарное дерево — это дерево, где каждый уровень (кроме, возможно, последнего) полностью заполнен, а все узлы на последнем уровне расположены как можно левее.

Мы можем представить каждую глубину дерева как "уровень", как если бы дерево было зданием, где корень — это верхний этаж, а ребра — это лестницы вниз к более низкому этажу.

Пример BFS на дереве

Поиск в ширину, выполненный на дереве ниже, обойдет узлы в том же порядке, что и их значения. Мы посещаем все узлы на глубине d перед тем, как перейти к узлам на глубине d + 1.

Когда использовать BFS, а когда DFS?

Мы упоминали ранее, что во многих задачах не важно, использовать ли обход в порядке preorder, inorder или postorder DFS. Главное, чтобы все узлы были посещены. Если у вас такая задача, то не имеет значения, использовать ли BFS, потому что каждое посещение узла сохранит достаточно информации независимо от порядка.

Однако, есть задачи, в которых BFS имеет больше смысла. Обычно это относится к задачам, где требуется обработать узлы по уровням. Например:

• Поиск кратчайшего пути в графе.
• Алгоритмы, работающие с уровнями дерева или графа.

В интервью вас могут спросить о недостатках BFS и DFS. Основной недостаток DFS — это то, что вы можете тратить много времени, исследуя ненужные узлы. Например, если значение, которое вы ищете, находится в правом потомке корня, а вы исследуете сначала левую часть дерева, вы потратите много времени. Основной недостаток BFS — если искомый узел находится глубоко, вам придется обходить все уровни, чтобы до него добраться.

Сложность по памяти

• DFS: Использует пространство, пропорциональное высоте дерева (максимальной глубине).

  • В идеальном бинарном дереве: O(log n).
  • В несбалансированном дереве: O(n).

• BFS: Использует пространство, пропорциональное количеству узлов на самом широком уровне.

  • В идеальном бинарном дереве: O(n).

Реализация BFS

Для реализации BFS используется очередь. Вот общий формат кода

let printAllNodes = (root) => {
  let queue = [root];
  while (queue.length) {
    let nodesInCurrentLevel = queue.length;
    let nextQueue = [];

    for (let i = 0; i < nodesInCurrentLevel; i++) {
      let node = queue[i];

      // тут применяем какую-то логику
      console.log(node.val);

      // добавляем следующие уровни в очередь
      if (node.left) {
        nextQueue.push(node.left);
      }
      if (node.right) {
        nextQueue.push(node.right);
      }
    }

    queue = nextQueue;
  }
};

Примечание для JavaScript

JavaScript не поддерживает встроенную эффективную очередь, но можно обойти это, используя второй массив nextQueue для реализации BFS.

Общая логика

• В начале каждой итерации внутри while-цикла (в месте, где находится комментарий "обработка текущего уровня"), очередь содержит все узлы текущего уровня.
• В самом начале это только корень.

Мы используем цикл for для итерации по узлам текущего уровня. Перед итерацией сохраняется количество узлов текущего уровня (nodesInCurrentLevel), чтобы цикл не обрабатывал другие узлы. Этот цикл:

1. Посещает каждый узел текущего уровня.
2. Добавляет всех потомков узла (узлы следующего уровня) в очередь.

Так как мы удаляем элементы с левой стороны и добавляем на правую (на противоположных концах), после завершения for-цикла очередь будет содержать все узлы следующего уровня. Затем мы переходим к следующей итерации while-цикла, и процесс повторяется.

Временная сложность

• При наличии эффективной очереди операции dequeue и enqueue выполняются за O(1).
• Основная идея BFS: мы посещаем каждый узел только один раз. Следовательно:
  • Временная сложность: O(n * k), где:
    • n — общее количество узлов,
    • k — объем работы, выполняемой для каждого узла (обычно O(1)).

Задачи

https://leetcode.com/problems/binary-tree-right-side-view/description/
https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/
https://leetcode.com/problems/deepest-leaves-sum/description/
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/
https://leetcode.com/problems/average-of-levels-in-binary-tree/description/
https://leetcode.com/problems/even-odd-tree/description/