Interactive DFS Visualization
Graph Traversal
Watch how DFS traverses a graph, exploring as far as possible along each branch before backtracking.
Interactive Visualization:
Edge Types:
Step 0 of 44: Initial state
Maze Solving
See how DFS can be used to solve a maze by exploring one path at a time until the exit is found.
Interactive Visualization:
How DFS Solves Mazes: DFS explores one path as far as possible before backtracking. It uses a stack to keep track of positions to visit. When it reaches a dead end, it backtracks to the last position with unexplored paths. This continues until it finds the exit or exhausts all possibilities.
Step 0 of 59: Initial state
Cycle Detection
Explore how DFS can detect cycles in a graph by keeping track of vertices in the current recursion stack.
Interactive Visualization:
How DFS Detects Cycles: DFS keeps track of nodes in the current recursion stack. If we encounter a node that is already in the recursion stack, we've found a cycle. This is because there's a path from that node back to itself, which is the definition of a cycle.
Step 0 of 21: Initial state
Learning Objective
Visualize how depth-first search works through interactive examples of graph traversal, maze solving, and cycle detection.
Visualizing Depth-First Search
Depth-First Search can be easier to understand when you see it in action. These visualizations will help you grasp how DFS explores graphs and solves problems by going deep before going wide.
Graph Traversal
Watch how DFS traverses a graph, exploring as far as possible along each branch before backtracking.
Maze Solving
See how DFS can be used to solve a maze by exploring one path at a time until the exit is found.
Cycle Detection
Explore how DFS can detect cycles in a graph by keeping track of vertices in the current recursion stack.
Graph Traversal
Watch how DFS traverses a graph, exploring as far as possible along each branch before backtracking.
Interactive Visualization:
Edge Types:
Step 0 of 44: Initial state
How it works: Starting from a source vertex, DFS explores one of its neighbors, then one of that neighbor's neighbors, and so on, going as deep as possible. When it reaches a vertex with no unvisited neighbors, it backtracks to the previous vertex and explores other branches.
DFS Graph Traversal Properties
DFS graph traversal has several important properties:
- Depth-First Exploration: DFS explores as far as possible along each branch before backtracking.
- Stack-Based: DFS uses a stack data structure (either explicitly or implicitly through recursion).
- Edge Classification: DFS can classify edges as tree edges, back edges, forward edges, or cross edges.
- Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
- Space Complexity: O(V) for the stack and visited set.
The visualization shows both recursive and iterative implementations of DFS. The recursive implementation uses the call stack, while the iterative implementation uses an explicit stack data structure.
Notice how DFS explores deeply along one path before backtracking, which is different from BFS's level-by-level exploration.