Широко търсене - Ръководство за обхождане на графики 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 Exception.

Процесът се повтаря отново със следващите елементи, които остават в опашката. В продължение на линиясе поддържа, за да ни даде списък с възли на всяко ниво в отделни свързани списъци.

637. Средно ниво на бинарно дърво (трудност: лесно)

Този въпрос ни казва да намерим средната стойност на възлите на всяко ниво на двоично дърво в масив. Това следва същата процедура като нашия предишен проблем с малко ощипване.

Както можете да видите, всичко, което направихме, беше да копираме и поставим кода на шаблона. След това просто поставяме променлива сума в цикъла for, която може да ни даде сумата от стойностите на възлите на всяко ниво. Това ще използваме, за да изчислим желаната от нас средна стойност.

429. Преминаване на ред на ниво N-дърво (трудност: средно)

Дърво, в което всеки възел има не повече от N броя деца, се нарича N-арно дърво.

Това следва точно същата процедура като обхождането на двоично дърво, с изключение на факта, че тук вмъкваме всички дъщери на възел в опашката. Не забравяйте, че докато решаваме проблеми, свързани с двоично дърво, ние сме вмъкнали само лявото и дясното подчинение на който и да е възел в опашката.

Това е всичко! Надявам се, че това ви е помогнало да разберете по-добре BFS и че сте се насладили на урока. Моля, препоръчайте тази публикация, ако смятате, че тя може да бъде полезна за някой друг!