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.The textbook definition:
Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph. Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.
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