Try it yourself

Run this code directly in your browser. Click "Open in full editor" to experiment further.

Loading...

Click Run to see output

Or press Ctrl + Enter

How it works

Ready to go deep? Depth-First Search (DFS) is an amazing algorithm for exploring graphs and trees! 🤿

How It Works

Imagine you're exploring a giant maze. Instead of looking at every intersection around you (like BFS), you pick one path and run down it as far as you possibly can until you hit a dead end! Once you're completely stuck, you turn around (we call this backtracking) and try the next available path.

To remember where we need to backtrack to, we use a Stack (think of a stack of pancakes 🥞 – Last-In, First-Out).

1. Recursive Approach: This is the elegant way. We just let Python's built-in function-call stack do the heavy lifting for us!

2. Iterative Approach: We build our own Stack using a simple Python list. We just .append() to add, and .pop() to pull from the top!

Like always with graphs, we carry a visited notepad so we don't accidentally run in circles forever! 😅

Time and Space Complexity

Time Complexity: O(V + E) — V is our vertices (nodes) and E is our edges. We visit every single room and hallway in the maze exactly once!

Space Complexity: O(V) — To store our visited notepad and our Stack of path choices.

Real World Magic

Solving Puzzles: Need to write code to solve a Sudoku puzzle or escape a maze? DFS and backtracking are your best friends!

Topological Sorting: Figuring out the order you need to take college classes based on prerequisites.

Finding Cycles: Checking to make sure a path doesn't loop back on itself (like detecting a dead-lock in a database).

Have fun running the code and tracing the paths it takes! 🎉

Related examples

Algorithms

Breadth-First Search (BFS) in Python

Learn Breadth-First Search (BFS) in Python! A beginner-friendly, fun guide to exploring graphs level by level.

Data Structures

Binary Tree in Python

Learn Binary Trees in Python! A fun, beginner-friendly guide to building trees, inserting nodes, and exploring inorder, preorder, and postorder traversals.