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