While Breadth-First Search (BFS) explores level by level, like a meticulous cartographer mapping the entire coastline before venturing inland, Depth-First Search (DFS) dives deep into one path until it hits a dead end or finds its goal. Imagine it as an intrepid explorer who, upon finding a promising trail, follows it as far as it goes before backtracking and trying another. This 'dive deep' strategy often employs recursion, making it a natural fit for many problems.
The core idea behind DFS is to explore as far as possible along each branch before backtracking. When we visit a node, we immediately explore one of its unvisited neighbors. We continue this process recursively. If we reach a point where all neighbors of the current node have been visited, or if we've explored a complete path, we backtrack to the previous node and try a different unexplored branch. This can be elegantly implemented using a recursive function.
function dfs(node, visited) {
visited.add(node);
console.log(`Visiting node: ${node}`);
for (const neighbor of getNeighbors(node)) {
if (!visited.has(neighbor)) {
dfs(neighbor, visited);
}
}
}Let's visualize this recursive descent. Imagine a simple graph. We start at a node, mark it as visited, and then pick one of its unvisited neighbors. We then call the DFS function on that neighbor. This creates a stack of function calls, with each call representing a step deeper into the graph. When a recursive call returns (meaning it has explored all reachable nodes from its starting point), we 'pop' that call from the stack and resume exploration from the previous node.
graph TD;
A --> B;
A --> C;
B --> D;
B --> E;
C --> F;
D --> G;
subgraph DFS Exploration
start(Start at A)
visitA(Visit A)
exploreB(Explore B)
visitB(Visit B)
exploreD(Explore D)
visitD(Visit D)
exploreG(Explore G)
visitG(Visit G)
backtrackD(Backtrack from G)
backtrackB(Backtrack from D)
exploreE(Explore E)
visitE(Visit E)
backtrackE(Backtrack from E)
backtrackA(Backtrack from B)
exploreC(Explore C)
visitC(Visit C)
exploreF(Explore F)
visitF(Visit F)
backtrackF(Backtrack from F)
backtrackC(Backtrack from C)
end(End)
start --> visitA
visitA --> exploreB
exploreB --> visitB
visitB --> exploreD
exploreD --> visitD
visitD --> exploreG
exploreG --> visitG
visitG --> backtrackD
backtrackD --> backtrackB
backtrackB --> exploreE
exploreE --> visitE
visitE --> backtrackE
backtrackE --> backtrackA
backtrackA --> exploreC
exploreC --> visitC
visitC --> exploreF
exploreF --> visitF
visitF --> backtrackF
backtrackF --> backtrackC
backtrackC --> end
end
This recursive nature makes DFS particularly useful for problems where you need to find a path, such as maze solving, or to explore all possible permutations or combinations. The 'visited' set is crucial to prevent infinite loops in graphs with cycles.
While recursion offers an elegant solution, a stack can also be used to implement DFS iteratively, mimicking the call stack. This can be beneficial for very deep search trees where exceeding the maximum recursion depth might be a concern.
function iterativeDfs(startNode, visited) {
const stack = [startNode];
visited.add(startNode);
while (stack.length > 0) {
const currentNode = stack.pop();
console.log(`Visiting node: ${currentNode}`);
for (const neighbor of getNeighbors(currentNode)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
}