Depth-First Search (DFS)

How Depth-First Search Works

1. Initialize

Start at the start node and explore as far as possible along each branch before backtracking.

💡 Pro Tip: DFS uses a stack (recursion) to explore deep into the graph.

2. Visit Node

Mark the current node as visited and add it to the path.

💡 Pro Tip: Nodes are visited in depth-first order.

3. Explore Neighbors

For each unvisited neighbor, recursively visit it.

💡 Pro Tip: DFS explores as deep as possible before backtracking.

4. Repeat

Continue until the end node is found or all nodes are visited.

💡 Pro Tip: The process repeats until the path is found or all nodes are explored.

5. Reconstruct Path

Trace back from the end node to the start node to get the path.

💡 Pro Tip: The found path is highlighted.

Key Concepts

Stack/Recursion

DFS uses a stack or recursion to explore as deep as possible before backtracking.

Depth Exploration

DFS explores one branch fully before moving to the next.

Not Always Shortest

DFS does not guarantee the shortest path in all graphs.

Legend

Start Node

Click and drag to move

End Node

Click and drag to move

Wall

Click to add/remove

Visited Nodes

Path Found

How to Use

1. Create Your Maze

Click or drag on the grid to add or remove walls

2. Position Start & End

Drag the green and red nodes to set start and end points

3. Visualize

Click "Visualize DFS" to see the path found by DFS

4. Experiment

Try different mazes and see how DFS explores the grid

About DFS

Depth-First Search (DFS) explores as deep as possible before backtracking. It does not always find the shortest path.

🧭

Exploratory

DFS explores deep into the graph before backtracking

🔄

Recursive

DFS is often implemented recursively

⚠️

Not Always Shortest

DFS may not find the shortest path in all cases

Depth-First Search does not guarantee the shortest path. "Stack" is used to explore as deep as possible before backtracking.