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:
| BFS | DFS | |
|---|---|---|
| Plná forma | BFS znamená Breadth First Search. | DFS znamená Depth First Search. |
| Technika | Je to technika založená na vrcholoch na nájdenie najkratšej cesty v grafe. | Je to technika založená na hranách, pretože vrcholy pozdĺž hrany sa skúmajú najskôr od počiatočného po koncový uzol. |
| Definícia | BFS je technika prechodu, pri ktorej sa najprv preskúmajú všetky uzly rovnakej úrovne a potom sa presunieme na ďalšiu úroveň. | DFS je tiež technika prechodu, pri ktorej sa prechod začína od koreňového uzla a skúmajú sa uzly tak ďaleko, ako je to možné, až kým nedosiahneme uzol, ktorý nemá žiadne nenavštívené susedné uzly. |
| Dátová štruktúra | Na prechod BFS sa používa dátová štruktúra frontu. | Na prechod BFS sa používa dátová štruktúra zásobníka. |
| Backtracking | BFS nepoužíva koncept spätného sledovania. | DFS používa backtracking na prechod cez všetky nenavštívené uzly. |
| Počet hrán | BFS nájde najkratšiu cestu s minimálnym počtom hrán na prechod zo zdroja do cieľového vrcholu. | V DFS je potrebný väčší počet hrán na prechod zo zdrojového vrcholu do cieľového vrcholu. |
| Optimalita | BFS traversal je optimálny pre tie vrcholy, ktoré sa majú hľadať bližšie k zdrojovému vrcholu. | Priebeh DFS je optimálny pre tie grafy, v ktorých sú riešenia vzdialené od zdrojového vrcholu. |
| Rýchlosť | BFS je pomalší ako DFS. | DFS je rýchlejší ako BFS. |
| Vhodnosť pre rozhodovací strom | Nie je vhodný pre rozhodovací strom, pretože vyžaduje najprv preskúmať všetky susedné uzly. | Je vhodný pre rozhodovací strom. Na základe rozhodnutia skúma všetky cesty. Keď je cieľ nájdený, zastaví jeho prechod. |
| Pamäťovo efektívne | Nie je pamäťovo efektívny, pretože vyžaduje viac pamäte ako DFS. | Je pamäťovo efektívny, pretože vyžaduje menej pamäte ako BFS. |