BFS și DFS sunt metodele de traversare utilizate în căutarea unui grafic. Traversarea grafurilor este procesul de vizitare a tuturor nodurilor din grafic. Un grafic este un grup de Vertices 'V' și Edges 'E' conectând la vârfuri.
Diagramă de comparație
| Bazele de comparație | BFS | DFS |
|---|---|---|
| De bază | Vertex-based algoritm | Edge-based algoritm |
| Structura de date utilizată pentru stocarea nodurilor | Coadă | Grămadă |
| Consumul de memorie | Ineficace | Eficient |
| Structura arborelui construit | Larg și scurt | Îngust și lung |
| Traversarea modei | Cele mai vechi vârfuri nevăzute sunt explorate la început. | Vertexurile de-a lungul marginii sunt explorate la început. |
| optimalitate | Optimal pentru găsirea celei mai scurte distanțe, nu în cost. | Nu este optimă |
| cerere | Examinează graficul bipartit, componenta conectată și calea cea mai scurtă prezentă într-un grafic. | Examinează graficul conectat pe două muchii, graficul puternic conectat, graficul aciclic și ordinea topologică. |
Definiția BFS
Breadth First Search (BFS) este metoda de traversare utilizată în grafice. Utilizează o coadă pentru stocarea vârfurilor vizitate. În această metodă accentul se pune pe vârful graficului, la început este selectat un vertex, apoi este vizitat și marcat. Vârfurile adiacente vârfului vizitat sunt apoi vizitate și stocate în coadă secvențial. În mod similar, nodurile stocate sunt apoi tratate unul câte unul, iar nodurile adiacente sunt vizitate. Un nod este explorat pe deplin înainte de a vizita orice alt nod din grafic, cu alte cuvinte, trece mai întâi nodurile mai neexplorate.
Exemplu
Avem un grafic al cărui vârfuri sunt A, B, C, D, E, F, G. Considerând A ca punct de plecare. Pașii implicați în acest proces sunt:
- Vertexul A este extins și stocat în coadă.
- Vertexele B, D și G ale succesoarelor lui A sunt extinse și stocate în coadă, între timp Vertex A eliminat.
- Acum B la capătul frontal al coada de așteptare este înlăturat împreună cu stocarea vârfurilor succesoare E și F.
- Vertexul D este la capătul frontal al coadajului, iar nodul F conectat este deja vizitat.
- Vertexul G este eliminat din coadă și are succesorul E, care este deja vizitat.
- Acum, E și F sunt îndepărtate din coadă, iar punctul său succesor 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.
- Producția generată este - A, B, D, G, E, F, C.
BFS poate fi util pentru a afla dacă graficul are componente conectate sau nu. Și poate fi folosit și pentru detectarea unui grafic bipartit .
Un grafic este bipartit când vârfurile de graf sunt divizate în două seturi disjuncte; nici două noduri adiacente nu ar locui în același set. O altă metodă de a verifica un grafic bipartit este de a verifica apariția unui ciclu ciudat în grafic. Un grafic bipartit nu trebuie să conțină un ciclu ciudat.
BFS este, de asemenea, mai bine la găsirea celei mai scurte căi din grafic ar putea fi văzută ca o rețea.
Definiția DFS
Metoda de traversare în primă căutare (DFS) utilizează stivă pentru stocarea vârfurilor vizitate. DFS este metoda bazată pe margini ș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, iar cele mai adânci noduri neexplicate sunt traversate la început. DFS traversează / vizitează fiecare vertex exact o dată și fiecare margine este inspectată exact de două ori.
Exemplu
Similar cu BFS permiteți să luați același grafic pentru efectuarea operațiilor DFS, iar pașii implicați sunt:
- Considerând A drept punctul de pornire care este explorat și stocat în teancul.
- B-ul succesorului B al A este stocat în teanc.
- Vertexul B are doi succesori E și F, printre care alfabetic E este explorat mai întâi și stocat în teanc.
- Succesorul vârfului E, adică G, este stocat în teanc.
- Vertex G are două vârfuri conectate, ambele fiind deja vizitate, astfel că G este scos din stivă.
- În mod similar, E este de asemenea eliminat.
- Acum, vârful B se află în partea de sus a stivei, un alt nod (vertex) F este explorat și stocat în teanc.
- Vertex F are doi succesori C și D, între ei C este traversat mai întâi și stocat în teanc.
- Vertex C are doar un predecesor care este deja vizitat, deci este scos din stiva.
- Acum, vârful D conectat la F este vizitat și stocat în teanc.
- Cum vertexul D nu are noduri nevizate, deci D este eliminat.
- În mod similar, F, B și A sunt de asemenea descoperite.
- Ieșirea generată este - A, B, E, G, F, C, D.
Aplicațiile DFS includ examinarea grafului conectat la două muchii, graficul conectat puternic, graficul aciclic și ordinea topologică .
Un grafic este numit două margini 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, unde defectarea unei legături î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 perechile ordonate de vârfuri. DFS este folosit î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 algoritmul bazat pe vertex, în timp ce DFS este un algoritm bazat pe margini.
- Structura datelor de 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. Spre deosebire de acestea, BFS construiește un arbore larg și scurt.
Concluzie
BFS și DFS, ambele tehnici de căutare a graficului au un timp de funcționare similar, dar consumul de spațiu diferit, DFS are spațiu liniar, deoarece trebuie să ne amintim o singură cale cu noduri neexplorate, în timp ce BFS păstrează fiecare nod din memorie.
DFS oferă 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ă la început obiectivul optim.
