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

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

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

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

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

Какво е Graph traversals?

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

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

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

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

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

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

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

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

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

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

Стъпка 1)

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

Стъпка 2)

В случай, че няма достъп до върха V, добавете върха 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-First in First Out) структура на данни се използва от BFS.
• Маркирате всеки възел в графиката като основен и започвате да обхождате данните от него.
• BFS преминава през всички възли в графиката и продължава да ги изпуска като завършени.
• BFS посещава съседен непосетен възел, маркира го като готов и го вмъква в опашка.
• Премахва предишния връх от опашката, в случай че не бъде намерен съседен връх.
• BFS алгоритъмът се повтаря, докато всички върхове в графиката бъдат преминати успешно и маркирани като завършени.
• Няма цикли, причинени от BFS по време на преминаването на данни от който и да е възел.

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

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

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

Oбобщение

• Обхождането на графиката е уникален процес, който изисква алгоритъмът да посети, провери и/или актуализира всеки един непосетен възел в дървовидна структура. Алгоритъмът BFS работи на подобен принцип.
• Алгоритъмът е полезен за анализиране на възлите в графика и конструиране на най-краткия път за преминаване през тях.
• Алгоритъмът обхожда графиката с най-малък брой итерации и възможно най-кратко време.
• BFS избира единичен възел (начална или изходна точка) в графика и след това посещава всички възли, съседни на избрания възел. BFS има достъп до тези възли един по един.
• Посетените и маркирани данни се поставят в опашка от BFS. Опашката работи на принципа първи влязъл, първи излязъл. Следователно елементът, поставен първи в графиката, първо се изтрива и се отпечатва като резултат.
• Алгоритъмът BFS никога не може да бъде хванат в безкраен цикъл.
• Благодарение на високата прецизност и стабилното изпълнение, BFS се използва в множество решения от реалния живот като P2P мрежи, уеб роботи и мрежово излъчване.