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