Definition
DFS is an algorithm for traversing a tree or graph.
We essentially follow a path until its end, then backtracks to the last branch before continuing.
DFS implementations are based on stacks, either implicitly (recursion) or explicitly (as with queues for BFS).
- Pros:
- At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance)
- Cons:
- It is possible that the found solution is not optimal
- At worst, this algorithm will explore every possible path before finding the solution