Какво представлява алгоритъмът на BFS (първоначално търсене на широчина)?
Широкото търсене (BFS) е алгоритъм, който се използва за графика на данни или търсене в дърво или обхождане на структури. Пълната форма на BFS е търсенето с ширина първо.
Алгоритъмът ефективно посещава и маркира всички ключови възли в графика по точен начин. Този алгоритъм избира един възел (начална или изходна точка) в графика и след това посещава всички възли, съседни на избрания възел. Не забравяйте, че BFS осъществява достъп до тези възли един по един.
След като алгоритъмът посети и маркира началния възел, той се придвижва към най-близките непосетени възли и ги анализира. Веднъж посетени, всички възли са маркирани. Тези повторения продължават, докато всички възли на графиката бъдат успешно посетени и маркирани.
В този урок по алгоритъм ще научите:
- Какво представлява алгоритъмът на BFS (първоначално търсене на широчина)?
- Какво представлява обхождането на графики?
- Архитектурата на BFS алгоритъма
- Защо се нуждаем от BFS алгоритъм?
- Как работи BFS алгоритъмът?
- Пример BFS алгоритъм
- Правила на алгоритъма на BFS
- Приложения на BFS алгоритъм
Какво представлява обхождането на графики?
Обхождането на графика е често използвана методология за локализиране на позицията на върха в графиката. Това е усъвършенстван алгоритъм за търсене, който може да анализира графиката със скорост и точност, заедно с маркиране на последователността на посетените върхове. Този процес ви позволява бързо да посетите всеки възел в графика, без да сте заключени в безкраен цикъл.
Архитектурата на BFS алгоритъма
- В различните нива на данните можете да маркирате всеки възел като начален или начален възел, който да започне обхождането. BFS ще посети възела и ще го маркира като посетен и ще го постави на опашката.
- Сега BFS ще посети най-близките и непосещавани възли и ще ги маркира. Тези стойности също се добавят към опашката. Опашката работи по модела FIFO.
- По подобен начин останалите най-близки и непосетени възли на графиката се анализират маркирани и се добавят към опашката. Тези елементи се изтриват от опашката при получаване и се отпечатват като резултат.
Защо се нуждаем от BFS алгоритъм?
Има много причини да използвате алгоритъма на BFS, който да използвате като търсене на вашия набор от данни. Някои от най-важните аспекти, които правят този алгоритъм вашият първи избор, са:
- BFS е полезен за анализ на възлите в графика и изграждане на най-краткия път на преминаване през тях.
- BFS може да премине през графика в най-малкия брой итерации.
- Архитектурата на алгоритъма BFS е проста и стабилна.
- Резултатът от алгоритъма BFS поддържа високо ниво на точност в сравнение с други алгоритми.
- BFS итерациите са безпроблемни и няма възможност този алгоритъм да се забърка в проблем с безкраен цикъл.
Как работи BFS алгоритъмът?
Обръщането на графика изисква алгоритъмът да посещава, проверява и / или актуализира всеки отделен непосетен възел в дървовидна структура. Обхожданията на графики се категоризират по реда, в който посещават възлите на графиката.
BFS алгоритъмът стартира операцията от първия или началния възел в графика и я обхожда изцяло. След като успешно премине първоначалния възел, следващият непроходим връх в графиката се посещава и маркира.
Следователно можете да кажете, че всички възли, съседни на текущия връх, се посещават и обхождат в първата итерация. За прилагане на работата на алгоритъм на BFS се използва проста методология на опашката, която се състои от следните стъпки:
Етап 1)
Всеки връх или възел в графиката е известен. Например можете да маркирате възела като V.
Стъпка 2)
В случай, че връх V не е достъпен, добавете върха V в BFS Queue
Стъпка 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 алгоритъм:
- BFS използва структура от данни на опашка (FIFO-First in First Out).
- Маркирате всеки възел в графиката като корен и започвате да обхождате данните от него.
- BFS обхожда всички възли в графиката и продължава да ги изпуска като завършени.
- BFS посещава съседен непосетен възел, маркира го като свършен и го вмъква в опашка.
- Премахва предишния връх от опашката, в случай че не бъде намерен съседен връх.
- Алгоритъмът на BFS се повтаря, докато всички върхове в графиката бъдат успешно преминати и маркирани като завършени.
- Няма цикли, причинени от BFS по време на обхождането на данни от който и да е възел.
Приложения на BFS алгоритъм
Нека да разгледаме някои от реалните приложения, при които внедряването на алгоритъма на BFS може да бъде много ефективно.
- Непретеглени графики: BFS алгоритъмът може лесно да създаде най-краткия път и минимално обхващащо дърво, за да посети всички върхове на графиката във възможно най-кратко време с висока точност.
- P2P мрежи: BFS може да бъде внедрен, за да локализира всички най-близки или съседни възли в равнопоставена мрежа. Това ще намери необходимите данни по-бързо.
- Web Crawlers: Търсачките или уеб роботите могат лесно да изграждат множество нива на индекси, като използват BFS. Внедряването на BFS започва от източника, който е уеб страницата, и след това посещава всички връзки от този източник.
- Навигационни системи: BFS може да ви помогне да намерите всички съседни местоположения от основното или местоположението на източника.
- Мрежово излъчване: Излъчваният пакет се ръководи от алгоритъма BFS, за да намери и достигне до всички възли, за които има адреса.
Обобщение
- Обръщането на графика е уникален процес, който изисква алгоритъмът да посещава, проверява и / или актуализира всеки един непосетен възел в дървовидна структура. Алгоритъмът на BFS работи на подобен принцип.
- Алгоритъмът е полезен за анализ на възлите в графика и конструиране на най-краткия път на преминаване през тях.
- Алгоритъмът обхожда графиката с най-малък брой итерации и възможно най-кратко време.
- BFS избира един възел (начална или изходна точка) в графика и след това посещава всички възли, съседни на избрания възел. BFS осъществява достъп до тези възли един по един.
- Посетените и маркирани данни се поставят на опашка от BFS. Опашката работи на база първи в първи изход. Следователно елементът, поставен първо в графиката, първо се изтрива и в резултат се отпечатва.
- Алгоритъмът на BFS никога не може да бъде хванат в безкраен цикъл.
- Благодарение на висока прецизност и стабилна реализация, BFS се използва в множество реални решения като P2P мрежи, Web Crawlers и Network Broadcasting.