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