Въведение в алгоритма на BFS
За ефективен достъп и управление на данните, те могат да се съхраняват и организират в специален формат, известен като структура на данните. Има много структури от данни като стек, масив, свързан списък, опашки, дървета и графики и др. В линейните структури от данни, като Stack, Array, Linked List и Queue, данните се организират в линеен ред, докато в не- линейни структури от данни като дървета и графики, данните се организират йерархично, не в последователност. Графиката е нелинейна структура на данни, която има възли и ръбове. Възлите в графика също могат да бъдат посочени като върхове, които са с ограничен брой, а ръбовете са свързващите линии между всеки два възела.
В горната графика върховете могат да бъдат представени като V = (A, B, C, D, E) и ръбовете могат да бъдат определени като
E = (AB, AC, CD, BE)
Какво е алгоритъмът на BFS?
Обикновено има два алгоритма, които се използват за преминаване на графика. Те са BFS (Breadth-First Search) и DFS (Depth First Search) алгоритми. Преминаването на графиката се посещава точно веднъж на всеки връх или възел и ръб, в добре определен ред. Освен това е много важно да следите върховете, които са били посетени, така че една и съща върха да не се преминава два пъти. В алгоритъма за първо търсене на Breath първо преминаването започва от избран възел или източник и преминаването продължава през възлите, директно свързани с източника на възел. По-просто казано, в BFS алгоритъмът първо трябва да се движи хоризонтално и да премине текущия слой, след което да се премине към следващия слой.
Как работи алгоритъмът на BFS?
Нека вземем примера на графиката по-долу.
Важната задача е да се намери най-краткият път в графиката, докато се пресичат възлите. Когато преминем през графика, върхът преминава от неоткрито състояние в открито състояние и накрая става напълно открит. Трябва да се отбележи, че е възможно да се забиете в някакъв момент, докато преминавате през графика и възел може да бъде посетен два пъти. Така че можем да използваме метод за маркиране на възлите, след като той промени състоянието на неразкрито до напълно откриване.
Можем да видим на изображението по-долу, че възлите могат да бъдат маркирани в графиките, докато станат напълно открити, като ги маркират с черно. Можем да започнем от изходния възел и докато преминаването преминава през всеки възел, те могат да бъдат маркирани, за да бъдат идентифицирани.
Преминаването започва от върха и след това преминава към изходящите краища. Когато ръбът отива към неоткрита върха, той се маркира като открит. Но когато ръбът премине към напълно открита или открита върха, той се игнорира.
За насочена графика всеки ръб се посещава веднъж, а за насочена графика, той се посещава два пъти, т.е. веднъж, докато посещава всеки възел. Алгоритъмът, който ще се използва, се решава въз основа на това как се съхраняват откритите върхове. В алгоритъма на BFS опашката се използва там, където най-напред се открива най-старата върха и след това се разпространява през слоевете от началния връх.
Стъпки се изпълняват за алгоритъм на BFS
По-долу стъпките се изпълняват за BFS алгоритъм.
- В дадена графика нека започнем от върха, т.е. в горната диаграма тя е възел 0. Нивото, в което присъства този връх, може да бъде означен като Layer 0.
- Следващата стъпка е да намерите всички други върхове, които са в съседство с началния връх, т.е. възел 0 или непосредствено достъпен от него. Тогава можем да маркираме тези съседни върхове, които да присъстват в слой 1.
- Възможно е да се стигне до същия връх поради цикъл в графиката. Така че, ние трябва да пътуваме само до тези върхове, които трябва да присъстват в един и същи слой.
- След това се маркира родителският връх на текущия връх, в който се намираме. Същото трябва да се извърши за всички върхове на слой 1.
- След това следващата стъпка е да намерите всички онези върхове, които са един-единствен край от всички върхове, които са на слой 1. Този нов набор от върхове ще бъде на ниво 2.
- Горният процес се повтаря, докато всички възли не бъдат пресечени.
Пример:
Нека вземем примера на графиката по-долу и да разберем как работи BFS алгоритъмът. Обикновено в BFS алгоритъм се използва опашка за въвеждане в опашката на възлите, докато преминават през възлите.
В горната графика първо възелът 0 трябва да бъде посетен и този възел е поставен на опашка към опашката по-долу:
След като посетите възела 0, съседният възел от 0, 1 и 2 са поставени на опашка. Опашката може да бъде представена както по-долу: 
Тогава ще бъде посетен първият възел в опашката, която е 2. След посещаването на възел 2, опашката може да бъде представена както по-долу:
След като посетите възел 2, 5 ще бъде поставен на опашка и тъй като няма незапознати съседни възли за възел 5, въпреки че 5 е на опашка, но няма да бъде посещаван два пъти.
След това първият възел от опашката е 1, който ще бъде посетен. Съседните възли 3 и 4 са поставени на опашка. Опашката е представена както по-долу
На следващо място, първият възел от опашката е 5, а за този възел няма повече незабранени съседни възли. Същото важи и за възлите 3 и 4, за които също няма по-незабелязани съседни възли.
Така всички възли се преминават и накрая опашката става празна.
заключение
Алгоритъмът за търсене на широчина предлага някои големи предимства, за да го препоръчам. Едно от многото приложения на BFS алгоритъма е да се изчисли най-краткият път. Също така, той се използва в мрежите за намиране на съседни възли и може да бъде намерен в сайтове за социални мрежи, мрежово излъчване и събиране на боклук. Потребителите трябва да разберат изискването и модела на данните, за да го използват за по-добра производителност.
Препоръчителни статии
Това е ръководство за алгоритъма на BFS. Тук обсъждаме концепцията, работата, стъпките и примера за изпълнение в Алгоритма на BFS. Можете да разгледате и другите ни предложени статии, за да научите повече -
- Какво е алчен алгоритъм?
- Алгоритъм за проследяване на Рей
- Алгоритъм за цифров подпис
- Какво е Java в хибернация?
- Криптография с цифров подпис
- BFS VS DFS | Топ 6 разлики с инфографика