✅ Алгоритм BFS - Як це працює - Кроки та приклад алгоритму BFS

Вступ до алгоритму BFS

Вступ до алгоритму BFS

Для ефективного доступу до даних та їх управління можна зберігати та організовувати у спеціальному форматі, відомому як структура даних. Існує багато структур даних, таких як стек, масив, пов'язаний список, черги, дерева та графіки тощо. У лінійних структурах даних, таких як стек, масив, пов'язаний список та черга, дані впорядковуються у лінійному порядку, тоді як у не- лінійні структури даних, такі як Дерева та Графіки, дані організовані ієрархічно не в послідовності. Графік - це нелінійна структура даних, яка має вузли та ребра. Вузли на графіку можна також називати вершинами, які мають кінцеву кількість, а ребра є сполучними лініями між будь-якими двома вузлами.

На наведеному вище графіку вершини можуть бути представлені у вигляді V = (A, B, C, D, E), а ребра можуть бути визначені як

E = (AB, AC, CD, BE)

Що таке алгоритм BFS?

Зазвичай існує два алгоритми, які використовуються для обходу графіка. Це алгоритми BFS (пошук в першу ширину) та DFS (заглиблений перший пошук). Обхід Графіка відвідує рівно один раз кожну вершину чи вузол та край, у чітко визначеному порядку. Крім того, дуже важливо відслідковувати вершини, які були відвідані, щоб однакова вершина не проходила двічі. В алгоритмі «Перший пошук дихання» перехід починається з обраного вузла або вихідного вузла, а обхід продовжується через вузли, безпосередньо підключені до вихідного вузла. Простіше кажучи, в алгоритмі BFS слід спочатку горизонтально переміщатися та проходити поточний шар, після чого переходити до наступного шару.

Як працює алгоритм BFS?

Візьмемо для прикладу наведений нижче графік.

Важливе завдання - знайти найкоротший шлях у графіку під час обходу вузлів. Коли ми переходимо графік, вершина переходить з нерозкритого стану у відкритий стан і остаточно виявляється повністю. Слід зазначити, що можна застрягнути в якийсь момент під час проходу через графік і вузол можна відвідати двічі. Таким чином, ми можемо використовувати метод маркування вузлів після того, як він змінює стан нерозкритого до повного виявлення.

На наведеному нижче зображенні ми бачимо, що вузли можна позначати на графіках, коли вони повністю виявляються, позначаючи їх чорним кольором. Ми можемо почати з початкового вузла, і коли проходження проходить через кожен вузол, їх можна позначати, щоб їх можна було ідентифікувати.

Перехід починається з вершини, а потім рухається до вихідних країв. Коли край переходить до нерозкритої вершини, він позначається як виявлений. Але коли край переходить до повністю виявленої або виявленої вершини, він ігнорується.

Для спрямованого графа кожне ребро відвідується один раз, а для ненаправленого графа - його відвідують двічі, тобто один раз під час відвідування кожного вузла. Алгоритм, який буде використовуватися, визначається на основі зберігання виявлених вершин. В алгоритмі BFS використовується черга, де спочатку виявляється найстаріша вершина, а потім поширюється через шари від початкової вершини.

Етапи виконуються для алгоритму BFS

Наведені нижче кроки виконуються для алгоритму BFS.

У даному графіку почнемо з вершини, тобто на наведеній діаграмі це вузол 0. Рівень, на якому присутня ця вершина, можна позначити як рівень 0.
Наступним кроком є пошук усіх інших вершин, які примикають до початкової вершини, тобто вузла 0 або негайно доступного від нього. Тоді ми можемо позначити ці сусідні вершини, які будуть присутні на рівні 1.
Можна дійти до тієї ж вершини через цикл у графі. Отже, ми повинні подорожувати лише до тих вершин, які мають бути в одному шарі.
Далі позначена батьківська вершина поточної вершини, в якій ми знаходимося. Те ж саме слід виконати для всіх вершин на рівні 1.
Тоді наступним кроком є пошук усіх вершин, які є одним краєм від усіх вершин, які знаходяться на рівні 1. Цей новий набір вершин буде на другому рівні.
Вищеописаний процес повторюється, поки всі вузли не будуть пройдені.

Приклад:

Візьмемо для прикладу графік нижче та зрозуміємо, як працює алгоритм BFS. Як правило, в алгоритмі BFS використовується черга для введення черги у вузли під час обходу вузлів.

У наведеному вище графіку спочатку слід відвідати вузол 0, і цей вузол переведений у чергу до нижньої черги:

Після відвідування вузла 0 сусідній вузол 0, 1 і 2 вводиться в чергу. Черга може бути представлена нижче:

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

Після відвідування вузла 2, 5 буде встановлено в чергу, і оскільки для вузла 5 немає невідомих сусідніх вузлів, все-таки 5 знаходиться в черзі, але він не буде відвідуватися двічі.

Далі, перший вузол черги - 1, який буде відвідано. Суміжні вузли 3 і 4 в черзі. Черга представлена як нижче

Далі, перший вузол у черзі дорівнює 5, і для цього вузла більше не відвідуваних сусідніх вузлів. Те саме стосується і вузлів 3 і 4, для яких також немає більше небачених сусідніх вузлів.

Тож усі вузли проходять і, нарешті, черга стає порожньою.

Висновок

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

Алгоритм BFS - Як це працює - Кроки та приклад алгоритму BFS