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