Breadth First Search
BFS înseamnă Breadth First Search este o tehnică bazată pe vertexuri pentru găsirea celei mai scurte căi în graf. Folosește o structură de date de tip Queue (coadă) care urmărește primul intrat primul ieșit. În BFS, se selectează câte un vertex la un moment dat, atunci când este vizitat și marcat, apoi sunt vizitate și stocate în coadă cele adiacente acestuia. Este mai lent decât DFS.
Ex-
A / \ B C / / \ D E F
Lovitura este:
A, B, C, D, E, F
Depth First Search
DFS înseamnă Depth First Search este o tehnică bazată pe muchii. Folosește structura de date Stack (stivă), efectuează două etape, în primul rând vârfurile vizitate sunt împinse în stivă, iar în al doilea rând, dacă nu există niciun vârf, atunci vârfurile vizitate sunt scoase.
Ex-
A / \ B C / / \ D E F
Succesul este:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS |
|---|---|---|
| BFS reprezintă Breadth First Search. | DFS reprezintă Depth First Search. | |
| DFS(Depth First Search) utilizează structura de date Stack. | ||
| În DFS, s-ar putea să parcurgem mai multe muchii pentru a ajunge la un vertex de destinație de la o sursă. | ||
| DFS este mai potrivită atunci când există soluții departe de sursă. | ||
| BFS ia în considerare mai întâi toți vecinii și, prin urmare, nu este potrivit pentru arborii decizionali utilizați în jocuri sau puzzle-uri. | DFS este mai potrivit pentru probleme de jocuri sau puzzle-uri. Luăm o decizie, apoi explorăm toate căile prin această decizie. Și dacă această decizie duce la o situație de câștig, ne oprim. | Complexitatea în timp a DFS este, de asemenea, O(V + E) atunci când se utilizează lista de adiacență și O(V^2) atunci când se utilizează matricea de adiacență, unde V reprezintă vârfurile și E reprezintă marginile. |
Vă rugăm să consultați, de asemenea, BFS vs DFS pentru arbore binar pentru a vedea diferențele pentru o parcurgere a unui arbore binar.