Алгоритъм за първо търсене в ширина (BFS) с ПРИМЕР

Какво е BFS алгоритъм (търсене първо в ширина)?

Търсенето в ширина (BFS) е алгоритъм, който се използва за графично представяне на данни, търсене в дърво или преминаване през структури. Пълната форма на BFS е Breadth-first search (търсене в ширина).

Алгоритъмът ефективно посещава и маркира всички ключови възли в графика по точен широк начин. Този алгоритъм избира единичен възел (начална или изходна точка) в графика и след това посещава всички възли, съседни на избрания възел. Не забравяйте, че BFS има достъп до тези възли един по един.

След като алгоритъмът посети и маркира началния възел, той се придвижва към най-близките непосетени възли и ги анализира. Веднъж посетени, всички възли се маркират. Тези итерации продължават, докато всички възли на графиката бъдат успешно посетени и маркирани.

Какво е Graph traversals?

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

Архитектурата на алгоритъма BFS

1. В различните нива на данните можете да маркирате всеки възел като начален или начален възел, от който да започнете да преминавате. BFS ще посети възела, ще го маркира като посетен и ще го постави в опашката.
2. Сега BFS ще посети най-близките и непосетени възли и ще ги маркира. Тези стойности също се добавят към опашката. Опашката работи на FIFO модел.
3. По подобен начин, останалите най-близки и непосетени възли в графиката се анализират, маркират и добавят към опашката. Тези елементи се изтриват от опашката, когато бъдат получени, и се отпечатват като резултат.

Защо се нуждаем от BFS алгоритъм?

Има многобройни причини да използвате алгоритъма BFS за търсене в набора от данни. Някои от най-важните аспекти, които правят този алгоритъм ваш първи избор, са:

• BFS е полезен за анализиране на възлите в графика и конструиране на най-краткия път за преминаване през тях.
• BFS може да преминава през графика с най-малък брой итерации.
• Архитектурата на алгоритъма BFS е проста и стабилна.
• Резултатът от алгоритъма BFS притежава високо ниво на точност в сравнение с други алгоритми.
• Итерациите на BFS са безпроблемни и няма възможност този алгоритъм да бъде уловен в проблем с безкраен цикъл.

Как работи алгоритъмът BFS?

Обхождането на графиката изисква алгоритъмът да посещава, проверява и/или актуализира всеки един непосетен възел в дървовидна структура. Обхожданията на графиката се категоризират според реда, в който посещават възлите на графиката.

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

Следователно, може да се каже, че всички възли, съседни на текущия връх, се посещават и преминават в първата итерация. За реализиране на работата на BFS алгоритъм се използва проста методология на опашки, която се състои от следните стъпки:

Стъпка 1)

Всеки връх или възел в графиката е известен. Например, можете да маркирате възела като V.

Стъпка 2)

В случай че върхът V не е достъпен, тогава той се добавя към опашката BFS.

Стъпка 3)

Стартирайте BFS търсенето и след завършване маркирайте връх V като посетен.

Стъпка 4)

BFS опашката все още не е празна, следователно премахнете върха V на графиката от опашката.

Стъпка 5)

Извлечете всички останали върхове на графа, които са съседни на върха V.

Стъпка 6)

За всеки съседен връх, да речем V1, в случай че все още не е посетен, тогава добавете V1 към опашката BFS.

Стъпка 7)

BFS ще посети V1, ще го маркира като посетен и ще го изтрие от опашката.

Примерен BFS алгоритъм

Стъпка 1)

Имате графика от седем числа, вариращи от 0 до 6.

Стъпка 2)

0 или нула е маркиран като основен възел.

Стъпка 3)

0 се посещава, маркира и вмъква в структурата на данните на опашката.

Стъпка 4)

Останалите съседни на 0 и непосетени възли се посещават, маркират и вмъкват в опашката.

Стъпка 5)

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

Правила на BFS алгоритъма

Ето важни правила за използване на алгоритъма BFS:

• Опашка (FIFO – Първият влязъл, Първият излязъл) структура на данни се използва от BFS.
• Маркирате всеки възел в графиката като корен и започвате да обхождате данните от него.
• BFS обхожда всички възли в графа и запазва паданетоping ги като завършени.
• BFS посещава съседен непосетен възел, маркира го като готов и го вмъква в опашка.
• Премахва предишния връх от опашката, в случай че не е намерен съседен връх.
• Алгоритъмът BFS итерира, докато всички върхове в графа бъдат успешно преминати и маркирани като завършени.
• Няма цикли, причинени от BFS по време на преминаването на данни от който и да е възел.

Приложения на алгоритъма BFS

Нека да разгледаме някои от приложенията в реалния живот, при които прилагането на BFS алгоритъм може да бъде много ефективно.

• Непретеглени графики: Алгоритъмът BFS може лесно да създаде най-краткия път и минимално обхващащо дърво, за да посети всички върхове на графа за възможно най-кратко време с висока точност.
• P2P мрежи: BFS може да се използва за локализиране на всички най-близки или съседни възли в peer-to-peer мрежа. Това ще намери необходимите данни по-бързо.
• Уеб роботи: Търсачките или уеб роботите могат лесно да изградят множество нива на индекси, като използват BFS. Внедряването на BFS започва от източника, който е уеб страницата, и след това посещава всички връзки от този източник.
• Навигационни системи: BFS може да ви помогне да намерите всички съседни местоположения от основното или изходното местоположение.
• Мрежово излъчване: Излъченият пакет се ръководи от алгоритъма на BFS, за да намери и достигне до всички възли, за които има адреса.

Въпроси и Отговори