Beau

Okay, so we've spent a lot of time talking about graphs, and the *idea* of Depth-First Search. You know, the maze analogy, going down one path until you hit a dead end. But now we actually have to… code it. In Python. Which feels a little more real.

Jo

It is. But I think you'll find it's surprisingly elegant, especially the first way we'll tackle it: the recursive approach. It almost maps one-to-one with the definition we talked about.

Beau

Okay, so where do we start? We need a graph first, right?

Jo

Exactly. Let's use that adjacency list idea from the last section. A Python dictionary is perfect for this. The keys are the nodes, and the values are lists of their neighbors. So, something like `graph = {'A': ['B', 'C'], 'B': ['D'], ...}` and so on.

Beau

Right. 'A' is connected to 'B' and 'C'. Got it. So what does the function look like?

Jo

So, we'll define a function, let's call it `dfs_recursive`. It needs to know about the `graph`, the `node` we're currently on, and a way to track which nodes we've already `visited`. We can use a set for `visited` because checking if an item is in a set is super fast.

Beau

That's to prevent going in circles forever, I assume.

Jo

Precisely. That's our base case. The very first line inside the function is: `if node in visited: return`. Just stop. Don't do anything else.

Jo

If it's not visited, the first thing we do is add it to our visited set. `visited.add(node)`. Now we've officially been here. Then maybe we print the node's name to see our path. And then... here's the magic.

Jo

We loop through all the neighbors of the current node. For each neighbor, we just... call the same function. `dfs_recursive(graph, neighbor, visited)`.

Beau

Whoa, okay. So it calls itself. Wait. We talked about DFS using a stack. Where is the stack? I don't see us creating a list and appending to it.

Jo

Aha! That is the single most important concept here. In a recursive function, the *call stack* is your stack. Every time a function calls another function—or itself—Python puts the current state on hold and adds a new frame to this internal call stack. When a function finishes, it gets popped off the stack, and we return to where we were.

Beau

So the backtracking is just the functions returning. Okay, that's... that's actually pretty cool. But what if the graph is massive? I've heard you can hit a 'recursion depth limit'.

Jo

You can, and that's the perfect reason to learn the other way: the iterative approach. It's the same logic, but we manage the stack ourselves, explicitly.

Beau

So, we actually create a list and use it like a stack.

Jo

Exactly. We'll make a function, `dfs_iterative`. Inside, you create `stack = [start_node]`, and the same `visited = set()`. Then you have a `while stack:` loop. As long as the stack isn't empty, we keep going.

Jo

Inside the loop, you pop a node off the stack: `current_node = stack.pop()`. Then you check if it's been visited. If not, you add it to visited, process it... and then you loop through its neighbors and push them onto the stack.

Beau

Okay, that seems more direct. But what about... what about cycles? We've talked about detecting them. How does that fit in?

Jo

Great question. For cycle detection, just `visited` isn't enough. We need to know which nodes are currently in our recursion path, our current exploration stack. So we use a second set, let's call it `recursion_stack`.

Jo

When we enter the recursive function for a node, we add it to both `visited` and `recursion_stack`. Then, when we check its neighbors, if a neighbor is *already in the recursion_stack*, we've found a cycle. We've looped back on our current path.

Beau

Ah, okay. So `visited` is for the whole traversal, but `recursion_stack` is just for the path we're on *right now*.

Jo

You got it. And the crucial last step: once we've explored all the neighbors of a node and are about to return, we remove it from the `recursion_stack`. Because it's no longer on our current path. That's the backtracking part.

Beau

Okay, one last thing. All our examples are just nodes connecting. What about weighted graphs, where the edges have costs?

Jo

Simple change to our data structure. Instead of the adjacency list being `{'A': ['B', 'C']}`, it would be something like `{'A': [('B', 5), ('C', 3)]}`. A list of tuples, where each tuple is the neighbor and the weight.

Jo

Standard DFS doesn't really care about weights—it just explores paths. So the traversal logic is identical. But you'd use that weight information for other algorithms, like finding the shortest path, which often build *on top* of a traversal idea like DFS.

Beau

So, the implementation itself is agnostic to the weight. The structure just needs to hold it for when we need it later. That's way less complicated than I thought.

Jo

That's the beauty of it. Once you see the recursive and iterative patterns, you realize it's a very flexible tool you can adapt for all sorts of problems, from cycle detection to just... well, exploring a maze.