Visualize recursive path exploration using the LIFO Stack strategy.
Graph Config
Search Speed
Search Statistics
Visited Nodes0
Maximum Depth0
Exploration Map
Ready
Click a node to set as start point • Default is 'A'
LIFO Stack
Stack is empty
Traversal Order
DFS prioritizes depth by exploring one branch as far as possible before backtracking to the nearest unexplored neighbor.
Deconstructing Depth-First Search (DFS)
How this fundamental graph traversal algorithm explores paths to their absolute limit.
Quick Context: What is Depth-First Search?
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a selected root node and explores as far as possible along each branch before backtracking. It uses a stack (Last-In, First-Out) to keep track of which node to visit next.
The Core Idea: Go Deep, Then Backtrack
Imagine you're in a maze. Using a DFS strategy, you would pick one path and follow it until you hit a dead end. Only then would you backtrack to the last intersection and try a different, unexplored path. This is the essence of DFS.
1. Push to Stack: Start with a root node and push it onto the stack.
2. Pop and Visit: Pop a node from the top of the stack. If it hasn't been visited, mark it as visited.
3. Push Neighbors: Find all unvisited neighbors of the node you just popped. Push them onto the stack.
4. Repeat: Continue this process until the stack is empty. Because the stack is LIFO, the most recently discovered neighbor is the next one to be explored, forcing the search to go deeper.
Guided Experiments with the Visualizer
Follow the Stack: Click "Start Search" and then "Step". Watch the "LIFO Stack" panel on the right. When a node is visited, its neighbors are pushed onto the stack. The node at the very top of the stack is always the next one to be explored.
Observe Backtracking: Continue stepping. You will eventually reach a node with no unvisited neighbors (a "dead end"). At this point, the algorithm will pop from the stack again, effectively "backtracking" to a previous node to explore its other neighbors. This is visualized by the red "backtracking" node color.
Change the Graph Structure: Use the "Structure Type" dropdown to switch between a "Tree" and a "Grid". Notice how DFS behaves differently. In a grid with cycles, DFS can take much longer paths before finding all nodes, as it might explore a long, winding route before backtracking to a closer, unvisited node.
Change the Start Node: Before starting, click on a different node in the graph to set it as the start point. Run the search again and see how the traversal order changes completely.
Pseudocode (Iterative Version)
// Iterative DFS with a Stack
function DFS(graph, startNode) {
let stack = [startNode];
let visited = new Set();
while (stack.length > 0) {
let node = stack.pop();
if (!visited.has(node)) {
visited.add(node);
print("Visiting: " + node);
for (neighbor of graph.getNeighbors(node)) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
Use Cases & Comparison to BFS
DFS is excellent for tasks where you need to explore a path to its conclusion, such as:
Finding a path in a maze.
Topological sorting of a directed acyclic graph.
Detecting cycles in a graph.
Compared to Breadth-First Search (BFS), which explores level by level, DFS dives deep. This means DFS will find a solution that is far away from the root node much faster than BFS, but it is not guaranteed to find the *shortest* path.
Cheat sheet
Depth First Search
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a selected root node and explores as far as possible along each branch before backtracking. It uses a stack (Last-In, First-Out) to keep track of which node to visit next.