Breadth First Search
BFS staat voor Breadth First Search en is een vertex-gebaseerde techniek voor het vinden van het kortste pad in een grafiek. Het gebruikt een Queue datastructuur die first in first out volgt. Bij BFS wordt één vertex per keer geselecteerd wanneer deze wordt bezocht en gemarkeerd, waarna de aangrenzende worden bezocht en in de wachtrij worden opgeslagen. Het is langzamer dan DFS.
Ex-
A / \ B C / / \ D E F
Uitvoer is:
A, B, C, D, E, F
Depth First Search
DFS staat voor Depth First Search en is een rand-gebaseerde techniek. Het gebruikt de gegevensstructuur Stack, voert twee fasen uit, eerst worden de bezochte hoekpunten in de stack geduwd en als er geen hoekpunten zijn, worden de bezochte hoekpunten eruit gehaald.
Ex-
A / \ B C / / \ D E F
Uitvoer is:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS |
|---|---|---|
| BFS staat voor Breadth First Search. | DFS staat voor Depth First Search. | |
| BFS (Breadth First Search) gebruikt een gegevensstructuur in de vorm van een wachtrij voor het vinden van het kortste pad. | DFS (Depth First Search) maakt gebruik van de gegevensstructuur Stack. | |
| BFS kan worden gebruikt om het kortste pad met één bron te vinden in een ongewogen grafiek, omdat we bij BFS een hoekpunt bereiken met een minimaal aantal randen vanaf een bron hoekpunt. | In DFS kunnen we meer randen doorkruisen om een bestemmingspunt vanaf een bron te bereiken. | |
| BFS is geschikter om hoekpunten te zoeken die dichter bij de gegeven bron liggen. | DFS is geschikter wanneer er oplossingen zijn die van de bron af liggen. | |
| BFS beschouwt eerst alle buren en is daarom niet geschikt voor beslisbomen die in spellen of puzzels worden gebruikt. | DFS is meer geschikt voor spel- of puzzelproblemen. We nemen een beslissing, dan verkennen we alle paden door deze beslissing. En als deze beslissing tot een win-situatie leidt, stoppen we. | De tijdcomplexiteit van BFS is O(V + E) wanneer Adjacency List wordt gebruikt en O(V^2) wanneer Adjacency Matrix wordt gebruikt, waarbij V staat voor vertices en E staat voor edges. | De tijdcomplexiteit van DFS is ook O(V + E) wanneer Adjacency List wordt gebruikt en O(V^2) wanneer Adjacency Matrix wordt gebruikt, waarbij V staat voor vertices en E staat voor edges. |
Zie ook BFS vs DFS voor Binary Tree voor de verschillen voor een Binary Tree Traversal.