Пре него што погледамо разлике између БФС и ДФС, прво би требало да знамо о БФС и ДФС одвојено.

Шта је БФС?

БФС означава Претрага у ширину . Такође је познато као обилазак редоследа нивоа . Структура података реда се користи за прелазак у ширину прве претраге. Када користимо БФС алгоритам за прелазак у граф, можемо сматрати било који чвор као основни чвор.

Хајде да размотримо доњи графикон за прелазак у ширину прве претраге.

разлика између тигра и лава

Претпоставимо да сматрамо чвор 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 који је остао у стеку, би искочио из стека као што је приказано испод:

Као што можемо приметити на горњој слици да је стек празан. Дакле, овде морамо да зауставимо ДФС прелазак, а елементи који су одштампани су резултат ДФС преласка.

Разлике између БФС и ДФС

Следе разлике између БФС и ДФС: