DFS vs. BFS
So, should you use DFS or BFS when traversing a graph? Well, it depends. Let's look at some rules of thumb we can use to help make the decision.
Is the Solution Close to the Root?
If you have a good reason to believe the vertex you're looking for is close to the root (where you plan to start searching) then BFS should be faster.
Does the Graph Have Wide Levels?
Imagine a tree-like graph with 10 vertices on the first level. Each of those ten vertices point to another ten vertices. The number of vertices at each level would be:
level 0: 1
level 1: 10
level 2: 100
level 3: 1000
level 4: 10000
Because BFS stores each horizontal level in memory at the same time, you might run out of memory. DFS would likely be more memory efficient.
Is the Search Space Infinite?
In some searches, the graph has infinite size. For example, imagine a simulation of a game of chess.
The first level of the graph represents all the possible current moves, the next level all the possible 2nd moves, and this goes on forever, especially when you consider that there are possible loops within the game (moving a queen back and forth).
In these cases, true DFS is practically impossible, you would either be forced to:
- Use BFS
- Use another algorithm
- Put a limit on how far your DFS algorithm can search before returning