Skip to main content

Що таке обхід дерева в ширину (BFS)?

Структури данихJunior~1 хв читання
Запропонувати правку

Обхід дерева в ширину (BFS, Breadth-First Search) - це спосіб обходу дерева, за якого вузли відвідуються по рівнях, починаючи від кореня і рухаючись зліва направо на кожному рівні.

Як це працює

  1. Починаємо з кореня.
  2. Відвідуємо всі вузли першого рівня (дітей кореня).
  3. Потім усі вузли другого рівня, далі третього і так далі.
  4. Для зберігання порядку обходу використовується черга (FIFO).

Покроковий приклад

javascript
A / \ B C / \ \ D E F

Порядок обходу: A → B → C → D → E → F

Черга під час обходу:

javascript
1. [A] 2. [B, C] 3. [C, D, E] 4. [D, E, F] 5. [E, F] 6. [F] 7. []

Особливості BFS

  • Базується на черзі.
  • Добре підходить для пошуку найкоротшого шляху в неозважених графах.
  • Відвідує вузли пошарово, а не в глибину.

Підсумок

BFS - це обхід дерева по рівнях зверху вниз, що використовує чергу для запам'ятовування порядку вузлів, щоб спочатку обробляти вузли, близькі до кореня, а потім - глибші.

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

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

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

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