Широкий пошук - Посібник з обходу графіків BFS із 3 прикладами Leetcode

Широкий перший пошук (BFS) - це один з найпопулярніших алгоритмів пошуку або обходу дерева або структури даних графіків. У цьому підручнику ми коротко дізнаємось, як працює BFS, та дослідимо базовий шаблон, який може бути використаний для вирішення деяких середніх та простих проблем у Leetcode.

Давайте почнемо, чи не так?

Що таке "Ширина - перший пошук"?

Отже, всі ми знаємо, що графік - це набір вершин і ребер: G = {V, E}. Пройти графік означає впорядковано відвідати кожну вершину та кожне ребро рівно один раз .

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

Тому кожного разу, коли нас просять зробити обхід порядку порядку, ми можемо використовувати техніку BFS.

У BFS ми починали б обхід з 1 (кореневий вузол) і відвідували його дочірні вузли 8, 5 та 2. Ми зберігали б їх у тому порядку, в якому вони були відвідані. Це дозволило б нам відвідувати дочірні вузли спочатку 8 (тобто 6, 4 і 3), потім 5 (тобто нульові), а потім 2 (тобто 9) тощо.

Впровадження

Для реалізації BFS використовується структура даних черги . Черга зберігає вузол і позначає його як "відвіданий", поки не буде позначено всі сусідні вершини.

Черга слідує за методом First In First Out (FIFO). Це означає, що сусіди вузла будуть відвідуватися в тому порядку, в якому вони були вставлені.

Чарівне заклинання BFS:

  1. Додайте вузол до черги
  2. Видалити вузол
  3. Отримати невідвідані сусіди видаленого вузла, додати їх у чергу
  4. Повторюйте кроки 1, 2 та 3, доки черга не порожня.

А тепер давайте розглянемо деякі проблеми Leetcode і застосуємо те, що ми дізналися.

102. Обхід порядку бінарного дерева (складність: середній)

Питання просить нас пройти через графік та надрукувати вузли на кожному рівні у зв’язаному списку. Щоб вирішити це, нам потрібно лише застосувати наше магічне закляття!

Переконайтеся, що добре розумієте код, оскільки це основний шаблон, який ми використовуватимемо для вирішення багатьох проблем. Тож пройдемо це.

У наведеному вище коді ми спочатку вставили кореневий вузол у чергу. Поки черга не порожня, ми вилучили цей вузол із черги та вставили його лівий та правий дочірній ряд у чергу.

Але перед цим ми перевірили, чи є кожна з його дочірніх категорій нульовою чи ні. Якщо значення null, ми отримали б виняток Null Pointer.

Процес повторюється знову з наступними елементами, які залишаються в черзі. Цикл forпідтримується, щоб надати нам список вузлів на кожному рівні в окремих пов'язаних списках.

637. Середнє рівня в двійковому дереві (складність: легко)

Це питання підказує нам знайти середнє значення вузлів на кожному рівні двійкового дерева в масиві. Це слідує тій самій процедурі, що і наша попередня проблема з невеликим налаштуванням.

Як бачите, все, що ми зробили, - це скопіювати та вставити код шаблону. Тоді ми просто поміщаємо змінну суми в цикл for, яка може дати нам суму значень вузлів на кожному рівні. Це те, що ми будемо використовувати для обчислення бажаного середнього значення.

429. Обхід ордера на рівні N-дерева (Складність: Середній)

Дерево, в якому кожен вузол має не більше N кількості дітей, називається N-арним деревом.

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

Це все! Сподіваюся, це допомогло вам краще зрозуміти BFS і що вам сподобався підручник. Будь ласка, порекомендуйте цю публікацію, якщо ви вважаєте, що вона може бути корисною для когось іншого!