Увод у алгоритам БФС-а
Да бисте ефикасно приступили подацима и управљали њима, они се могу чувати и организовати у посебном формату познатом као структура података. Постоје многе структуре података као што су Стацк, Арраи, Повезана листа, Куеуес, Дрвеће и Графови итд. У линеарним структурама података, као што су Стацк, Арраи, Линкед Лист и Куеуе, подаци су организовани у линеарном редоследу, док се у не- линеарне структуре података попут дрвећа и графова, подаци су организовани хијерархијски не у низу. Граф је нелинеарна структура података која има чворове и ивице. Чворови у графикону могу се називати и врхови који су коначног броја и ивице су повезујуће линије између било која два чвора.
На горњем графикону, врхови се могу представити као В = (А, Б, Ц, Д, Е), а ивице се могу дефинисати као
Е = (АБ, АЦ, ЦД, БЕ)
Шта је БФС алгоритам?
Обично постоје два алгоритма која се користе за помицање графикона. То су БФС (Бреадтх-Фирст Сеарцх) и ДФС (Дептх Фирст Сеарцх) алгоритми. Помицање графикона долази у једном тачно једном вертексу или чвору и ивици, по добро дефинисаном редоследу. Такође, врло је важно пратити врхове који су били посећени како се два пута не би прелазили исти пут. У алгоритму Бреатх Фирст Сеарцх, кретање започиње од изабраног чвора или изворног чвора, а кретање се наставља кроз чворове који су директно повезани са изворним чвором. Једноставније речено, у БФС алгоритму се прво треба хоризонтално померати и прелазити тренутни слој након чега се врши прелазак на следећи слој.
Како функционира алгоритам БФС?
Узмимо за пример графикон доле.
Важан задатак који се тренутно налази је проналазак најкраћег пута у графикону током проласка кроз чворове. Када прелазимо граф, вертекс прелази из неоткривеног у откривено стање и коначно постаје потпуно откривен. Треба напоменути да је могуће да се заглави у неком тренутку док се кроз граф и чвор могу посетити два пута. Дакле, можемо користити методу обележавања чворова након што промени стање неоткривених до потпуно откривених.
На доњој слици можемо видети да чворови могу бити означени на графовима како бивају у потпуности откривени означавањем црном бојом. Можемо започети на изворном чвору и како пролазак напредује кроз сваки чвор, они могу бити означени да се идентификују.
Окретање полази од вертекса, а затим се креће до излазних ивица. Када ивица пређе на неоткривену вертексу, означава се као откривена. Али када ивица пређе на потпуно откривену или откривену границу, она се игнорише.
За усмјерени граф свака се ивица посјећује једном, а за неусмјерени граф двапут, једном приликом посјећивања сваког чвора. Алгоритам који ће се користити одлучује се на основу складиштења откривених врхова. У БФС алгоритму, ред се користи тамо где се најпре открије најстарија вертика, а затим се размножава кроз слојеве из почетне вертекса.
Кораци се изводе за БФС алгоритам
Следећи кораци се изводе за БФС алгоритам.
- У датом графу почнимо од вертекса, тј. На горњем дијаграму је то чвор 0. Ниво на коме је присутна та вршина може се означити као Лаиер 0.
- Сљедећи корак је проналажење свих осталих врхова који су сусједни почетном вертексу, тј. Чвору 0 или су му одмах доступни. Тада можемо обележити ове суседне врхове да буду присутни у Слоју 1.
- Могуће је доћи до исте верзије због петље у графикону. Дакле, требали бисмо путовати само до оних врхова који би требали бити присутни у истом слоју.
- Затим је означена надређена врхова тренутне вертике у којој се налазимо. Исто се мора извести за све врхове на нивоу 1.
- Затим је следећи корак проналажење свих оних врхова који су један ивице далеко од свих врхова који су на нивоу 1. Нови скуп вертикала биће на нивоу 2.
- Горњи поступак се понавља док се не пређу сви чворови.
Пример:
Узмимо за пример графикона доле и разумемо како функционише БФС алгоритам. Опћенито, у БФС алгоритму, ред се користи за ред на чворовима током проласка кроз чворове.
У горњем графикону прво треба посетити чвор 0 и тај чвор је додан у ред доњем реду:
Након посете чвору 0, суседни чворови 0, 1 и 2 постављају се у ред. Ред чекања може бити представљен на следећи начин: 
Тада ће бити посећен први чвор у реду који је 2. Након што је чвор 2 посећен, ред чекања може бити представљен као доле:
Након посете чвору 2, 5 ће се ставити у ред и пошто не постоје невиђени суседни чворови за чвор 5, и даље је 5 чак у реду, али неће бити посећен два пута.
Затим је први чвор у реду чекања 1 који ће бити посећен. Сусједни чворови 3 и 4 постављени су у ред. Ред чекања је представљен као доле
Даље, први чвор у реду је 5, а за овај чвор нема више невиђених сусједних чворова. Исто важи за чворове 3 и 4 за које такође нема више невиђених сусједних чворова.
Тако су сви чворови прешли и на крају, ред постаје празан.
Закључак
Алгоритам претраживања круга нуди неке велике предности за препоручивање. Једна од многих апликација БФС алгоритма је израчунавање најкраћег пута. Такође, користи се у умрежавању за проналажење сусједних чворова и може се наћи на друштвеним мрежама, мрежном преносу и одвозу смећа. Корисници морају да разумеју захтев и образац података да би га користили за боље перформансе.
Препоручени чланци
Ово је водич за БФС алгоритам. Овдје смо расправљали о концепту, раду, корацима и примјеру перформанси у БФС алгоритму. Можете и да прођете кроз друге наше Предложене чланке да бисте сазнали више -
- Шта је похлепни алгоритам?
- Алгоритам Раи Трацинг
- Алгоритам дигиталног потписа
- Шта је Јава хибернација?
- Криптографија дигиталног потписа
- БФС ВС ДФС | Топ 6 разлике са Инфографиком