Theory
Depth First Search, or DFS, explores one path as deeply as possible before backtracking. It can be implemented using recursion or an explicit stack. DFS is useful in graph traversal, cycle detection and many backtracking problems.
Example
function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
for (const next of graph[node]) {
dfs(graph, next, visited);
}
}
const graph = {
A: ["B", "C"],
B: ["D"],
C: [],
D: []
};
dfs(graph, "A");
Expected Output
All reachable nodes are visited using depth-first traversal.
Practice
Implement DFS using both recursion and a stack.
Interview Questions
- What is DFS?
- Which data structure can DFS use?
- What is the difference between BFS and DFS?
- Where is DFS useful?