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