diferența majoră dintre BFS și DFS este că BFS continuă nivel cu nivel în timp ce DFS urmează mai întâi o cale de la început la nodul final (vertex), apoi o altă cale de la început până la sfârșit și așa mai departe până când toate nodurile sunt vizitate. Mai mult, BFS folosește coada pentru stocarea nodurilor, în timp ce DFS folosește stiva pentru traversarea nodurilor.
BFS și DFS sunt metodele de traversare utilizate în căutarea unui grafic. Traversarea graficului este procesul de vizitare a tuturor nodurilor graficului. Un graf este un grup de noduri ‘V’ și muchii ‘E’ care se conectează la noduri.
conținut: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure din arborele construit | larg și scurt | îngust și lung |
| traversând moda | cele mai vechi vârfuri nevizitate sunt explorate la început. | nodurile de-a lungul marginii sunt explorate la început. |
| optimalitate | optim pentru a găsi cea mai scurtă distanță, nu în cost. | nu este optim |
| aplicație | examinează graficul bipartit, componenta conectată și calea cea mai scurtă prezentă într-un grafic. | examinează graficul conectat cu două margini, graficul puternic conectat, graficul aciclic și ordinea topologică. |
definiția BFS
width first Search (BFS) este metoda de traversare utilizată în grafice. Folosește o coadă pentru stocarea vârfurilor vizitate. În această metodă accentul este pe vârfurile graficului, un vârf este selectat la început, apoi este vizitat și marcat. Nodurile adiacente vertexului vizitat sunt apoi vizitate și stocate în coadă secvențial.în mod similar, vârfurile stocate sunt apoi tratate unul câte unul, iar vârfurile lor adiacente sunt vizitate. Un nod este explorat pe deplin înainte de a vizita orice alt nod din grafic, cu alte cuvinte, traversează mai întâi cele mai puțin adânci noduri neexplorate.
exemplu
avem un grafic ale cărui vârfuri sunt A, B, C, D, E, F, G. considerând A ca punct de plecare. Pașii implicați în proces sunt:
- vertexul A este extins și stocat în coadă.
- nodurile B, D și G succesorii lui A, sunt extinse și stocate în coada de așteptare între timp Vertex a eliminat.
- Acum B la capătul din față al cozii este eliminat împreună cu stocarea vârfurile succesoare E și F.
- Vertex D este la capătul frontal al cozii este eliminat, iar nodul său conectat F este deja vizitat.
- Vertex G este eliminat din coadă și are succesorul E care este deja vizitat.
- Acum E și F sunt eliminate din coadă, iar succesorul său vertex C este traversat și stocat în coadă.
- în cele din urmă C este, de asemenea, eliminat și coada este goală, ceea ce înseamnă că am terminat.
- ieșirea generată este – A, B, D, G, E, F, C.
Aplicații
BFS poate fi util în a găsi dacă graficul a conectat componente sau nu. Și, de asemenea, poate fi folosit în detectarea unui grafic bipartit.
un graf este bipartit atunci când nodurile grafului sunt împărțite în două seturi disjuncte; nu există două vârfuri adiacente în același set. O altă metodă de verificare a unui grafic bipartit este de a verifica apariția unui ciclu impar în grafic. Un graf bipartit nu trebuie să conțină ciclu impar.
BFS este, de asemenea, mai bine la găsirea calea cea mai scurtă în grafic ar putea fi văzută ca o rețea.
definiția DFS
metoda de parcurgere a primei căutări în adâncime (DFS) folosește stiva pentru stocarea vârfurilor vizitate. DFS este metoda bazată pe margine și funcționează în mod recursiv în care vârfurile sunt explorate de-a lungul unei căi (margine). Explorarea unui nod este suspendată de îndată ce se găsește un alt nod neexplorat și cele mai adânci noduri neexplorate sunt traversate în primul rând. DFS traversează / vizitează fiecare vârf exact o dată și fiecare margine este inspectată exact de două ori.
exemplu
Similar cu BFS permite să ia același grafic pentru efectuarea operațiunilor DFS, iar pașii implicați sunt:
- luând în considerare a ca vârf de pornire care este explorat și stocat în stivă.
- b succesor vertex A este stocat în stivă.
- Vertex B au doi succesori E și F, printre care alfabetic E este explorat mai întâi și stocat în stivă.
- succesorul vertex E, adică, G este stocat în stivă.
- Vertex G au două noduri conectate și ambele sunt deja vizitate, deci G este scos din stivă.
- în mod similar, E S, de asemenea, eliminate.
- acum, vârful B este în partea de sus a stivei, un alt nod(vertex) F este explorat și stocat în stivă.
- vertexul F are doi succesori C și D, între ei C este traversat mai întâi și stocat în stivă.
- Vertex C are un singur predecesor care este deja vizitat, deci este eliminat din stivă.
- acum vertex d conectat la F este vizitat și stocat în stivă.
- deoarece vertexul D nu are noduri nevizitate, prin urmare D este eliminat.
- în mod similar, F, B și a sunt, de asemenea, popped.
- ieșirea generată este – A, B, E, G, F, C, D.
aplicație
aplicațiile DFS includ inspecția a două grafice conectate la margine, grafic puternic conectat, grafic aciclic și ordine topologică.
un grafic se numește două muchii conectate dacă și numai dacă rămâne conectat chiar dacă una dintre marginile sale este îndepărtată. Această aplicație este foarte util, în rețelele de calculatoare în cazul în care eșecul de o legătură în rețea nu va afecta rețeaua rămasă, și ar fi încă conectat.
graficul puternic conectat este un grafic în care trebuie să existe o cale între perechea ordonată de vârfuri. DFS este utilizat în graficul direcționat pentru căutarea căii între fiecare pereche ordonată de vârfuri. DFS poate rezolva cu ușurință problemele de conectivitate.
diferențe cheie între BFS și DFS
- BFS este un algoritm bazat pe noduri, în timp ce DFS este un algoritm bazat pe margini.
- structura de date Coadă este utilizat în BFS. Pe de altă parte, DFS folosește stivă sau recursivitate.
- spațiul de memorie este utilizat eficient în DFS, în timp ce utilizarea spațiului în BFS nu este eficientă.
- BFS este algoritmul optim în timp ce DFS nu este optim.
- DFS construiește copaci înguste și lungi. Împotriva, BFS construiește copac larg și scurt.
concluzie
BFS și DFS, ambele tehnici de căutare a graficelor au un timp de funcționare similar, dar un consum de spațiu diferit, DFS are spațiu liniar pentru că trebuie să ne amintim o singură cale cu noduri neexplorate, în timp ce BFS păstrează fiecare nod în memorie.
DFS produce soluții mai profunde și nu este optimă, dar funcționează bine atunci când soluția este densă, în timp ce BFS este optimă, care caută obiectivul optim la început.