Predtým, ako sa pozrieme na rozdiely medzi BFS a DFS, mali by sme najprv vedieť o BFS a DFS samostatne.

čo je BFS?

BFS znamenať Prvé vyhľadávanie podľa šírky . Je tiež známy ako prechod na úrovni objednávky . Štruktúra údajov Queue sa používa na prechod podľa šírky prvého vyhľadávania. Keď použijeme algoritmus BFS na prechod v grafe, môžeme považovať akýkoľvek uzol za koreňový uzol.

Uvažujme nižšie uvedený graf pre šírku prvého prechodu vyhľadávania.

poradie náhodne v sql

Predpokladajme, že uzol 0 považujeme za koreňový uzol. Preto by sa prechod začal od uzla 0.

Po odstránení uzla 0 z frontu sa vytlačí a označí ako a navštívený uzol.

Keď sa uzol 0 odstráni z frontu, susedné uzly uzla 0 sa vložia do frontu, ako je znázornené nižšie:

Teraz bude uzol 1 odstránený z frontu; vytlačí sa a označí ako navštívený uzol

Akonáhle sa uzol 1 odstráni z frontu, všetky susedné uzly uzla 1 budú pridané do frontu. Susedné uzly uzla 1 sú 0, 3, 2, 6 a 5. Do frontu však musíme vložiť iba nenavštívené uzly. Keďže uzly 3, 2, 6 a 5 sú nenavštívené; preto budú tieto uzly pridané do frontu, ako je uvedené nižšie:

Ďalší uzol je 3 vo fronte. Takže uzol 3 bude odstránený z frontu, bude vytlačený a označený ako navštívený, ako je uvedené nižšie:

Akonáhle sa uzol 3 odstráni z frontu, potom sa všetky susedné uzly uzla 3 okrem navštívených uzlov pridajú do frontu. Susedné uzly uzla 3 sú 0, 1, 2 a 4. Keďže uzly 0, 1 sú už navštívené a uzol 2 je prítomný vo fronte; preto musíme do frontu vložiť iba uzol 4.

rozdiel medzi firmou a spoločnosťou

Teraz je nasledujúci uzol vo fronte 2. Takže 2 by sa vymazal z frontu. Vytlačí sa a označí ako navštívené, ako je uvedené nižšie:

Akonáhle sa uzol 2 odstráni z frontu, všetky susedné uzly uzla 2 okrem navštívených uzlov budú pridané do frontu. Susedné uzly uzla 2 sú 1, 3, 5, 6 a 4. Keďže uzly 1 a 3 už boli navštívené a 4, 5, 6 sú už pridané do frontu; preto do fronty nemusíme vkladať žiadny uzol.

Ďalším prvkom je 5. Čiže 5 by sa vymazalo z frontu. Vytlačí sa a označí ako navštívené, ako je uvedené nižšie:

Akonáhle bude uzol 5 odstránený z frontu, potom budú všetky susedné uzly uzla 5 okrem navštívených uzlov pridané do frontu. Susedné uzly uzla 5 sú 1 a 2. Pretože oba uzly už boli navštívené; preto neexistuje žiadny vrchol, ktorý by sa mal vložiť do frontu.

Ďalší uzol je 6. Takže 6 by bolo vymazané z frontu. Vytlačí sa a označí ako navštívené, ako je uvedené nižšie:

Akonáhle je uzol 6 odstránený z frontu, potom budú všetky susedné uzly uzla 6 okrem navštívených uzlov pridané do frontu. Susedné uzly uzla 6 sú 1 a 4. Pretože uzol 1 už bol navštívený a uzol 4 je už pridaný do fronty; preto nie je vrchol, ktorý sa má vložiť do frontu.

Ďalším prvkom vo fronte je 4. Takže 4 by sa z frontu vymazal. Vytlačí sa a označí ako navštívené.

Akonáhle bude uzol 4 odstránený z frontu, potom budú všetky susedné uzly uzla 4 okrem navštívených uzlov pridané do frontu. Susedné uzly uzla 4 sú 3, 2 a 6. Pretože všetky susedné uzly už boli navštívené; takže do fronty nie je možné vložiť žiadny vrchol.

Čo je DFS?

DFS znamená Depth First Search. Pri DFS traversal sa používa dátová štruktúra zásobníka, ktorá funguje na princípe LIFO (Last In First Out). V DFS môže byť prechádzanie spustené z ľubovoľného uzla, alebo môžeme povedať, že akýkoľvek uzol môže byť považovaný za koreňový uzol, kým koreňový uzol nie je uvedený v probléme.

V prípade BFS, prvku, ktorý je vymazaný z Queue, sú susedné uzly odstráneného uzla pridané do Queue. Na rozdiel od toho v DFS, prvok, ktorý sa odstráni zo zásobníka, sa potom do zásobníka pridá iba jeden susedný uzol vymazaného uzla.

Pozrime sa na nižšie uvedený graf pre prechod Hĺbka prvého vyhľadávania.

výhody a nevýhody technológie

Považujte uzol 0 za koreňový uzol.

rolovacie koliesko nefunguje

Najprv vložíme prvok 0 do zásobníka, ako je znázornené nižšie:

Uzol 0 má dva susedné uzly, t. j. 1 a 3. Teraz môžeme na prechod použiť iba jeden susedný uzol, buď 1 alebo 3. Predpokladajme, že uvažujeme uzol 1; preto sa 1 vloží do stohu a vytlačí sa, ako je znázornené nižšie:

Teraz sa pozrieme na susedné vrcholy uzla 1. Nenavštívené susedné vrcholy uzla 1 sú 3, 2, 5 a 6. Môžeme zvážiť ktorýkoľvek z týchto štyroch vrcholov. Predpokladajme, že vezmeme uzol 3 a vložíme ho do zásobníka, ako je znázornené nižšie:

Zvážte nenavštívené susedné vrcholy uzla 3. Nenavštívené susedné vrcholy uzla 3 sú 2 a 4. Môžeme vziať ktorýkoľvek z vrcholov, t. j. 2 alebo 4. Predpokladajme, že vezmeme vrchol 2 a vložíme ho do zásobníka, ako je znázornené nižšie:

Nenavštívené susedné vrcholy uzla 2 sú 5 a 4. Môžeme si vybrať ktorýkoľvek z vrcholov, t. j. 5 alebo 4. Predpokladajme, že vezmeme vrchol 4 a vložíme ho do zásobníka, ako je znázornené nižšie:

Teraz zvážime nenavštívené susedné vrcholy uzla 4. Nenavštívený susedný vrchol uzla 4 je uzol 6. Preto je prvok 6 vložený do zásobníka, ako je znázornené nižšie:

Po vložení prvku 6 do zásobníka sa pozrieme na nenavštívené susedné vrcholy uzla 6. Keďže neexistujú žiadne nenavštívené susedné vrcholy uzla 6, nemôžeme sa pohnúť za uzol 6. V tomto prípade vykonáme backtracking . Najvyšší prvok, t. j. 6, by sa vysunul zo stohu, ako je znázornené nižšie:

Najvyšší prvok v zásobníku je 4. Pretože z uzla 4 nezostali žiadne nenavštívené susedné vrcholy; preto sa uzol 4 vysunie zo zásobníka, ako je znázornené nižšie:

Ďalším najvyšším prvkom v zásobníku je 2. Teraz sa pozrieme na nenavštívené susedné vrcholy uzla 2. Keďže zostal iba jeden nenavštívený uzol, t. j. 5, uzol 5 by bol zatlačený do zásobníka nad 2 a vytlačí sa ako je ukázané nižšie:

Teraz skontrolujeme susedné vrcholy uzla 5, ktoré sú ešte nenavštívené. Keďže už nezostal žiadny vrchol, ktorý by sme mohli navštíviť, vytiahneme prvok 5 zo zásobníka, ako je znázornené nižšie:

Nemôžeme sa posunúť o ďalších 5, takže musíme vykonať backtracking. Pri backtrackingu by sa najvrchnejší prvok vysunul zo zásobníka. Najvyšší prvok je 5, ktorý by vyskočil zo zásobníka, a presunieme sa späť do uzla 2, ako je znázornené nižšie:

maven nainštalovať

Teraz skontrolujeme nenavštívené susedné vrcholy uzla 2. Keďže už nezostal žiadny susedný vrchol na návštevu, vykonáme backtracking. Pri backtrackingu by sa najvrchnejší prvok, t. j. 2, vysunul zo zásobníka a presunieme sa späť do uzla 3, ako je znázornené nižšie:

Teraz skontrolujeme nenavštívené susedné vrcholy uzla 3. Keďže už nezostal žiadny susedný vrchol na návštevu, vykonáme backtracking. Pri backtrackingu by sa najvrchnejší prvok, t. j. 3, vysunul zo zásobníka a presunieme sa späť do uzla 1, ako je znázornené nižšie:

Po vysunutí prvku 3 skontrolujeme nenavštívené susedné vrcholy uzla 1. Keďže už nezostal žiadny vrchol, ktorý by sme mohli navštíviť; preto sa vykoná spätné sledovanie. Pri backtrackingu by sa najvrchnejší prvok, t. j. 1, vysunul zo zásobníka a presunieme sa späť do uzla 0, ako je znázornené nižšie:

Skontrolujeme susedné vrcholy uzla 0, ktoré sú ešte nenavštívené. Keďže už nezostal žiadny susedný vrchol na návštevu, vykonáme spätné sledovanie. V tomto prípade by sa zo zásobníka vysunul iba jeden prvok, t. j. 0, ktorá zostala v zásobníku, ako je znázornené nižšie:

Ako môžeme vidieť na obrázku vyššie, zásobník je prázdny. Takže tu musíme zastaviť prechod DFS a prvky, ktoré sa vytlačia, sú výsledkom prechodu DFS.

Rozdiely medzi BFS a DFS

Nasledujú rozdiely medzi BFS a DFS: