Building the graph, and DFS without recursion

Building the graph you traverse

Lessons 7-1 and 7-2 handed you a ready-made adjacency dictionary, and real problems almost never do.

Interview inputs arrive as an edge list, meaning pairs like ("A", "B"), or as a grid, and the first minute of your solution is building the adjacency list.

Getting this step wrong, usually by forgetting one direction of an undirected edge, produces a traversal that silently misses half the graph. It fails quietly rather than loudly, which is why the step deserves its own drill.

The recipe has three steps.

1. Start an empty defaultdict(list), a dictionary that invents an empty list for any new key, which saves an if-statement per node.
2. For each edge (u, v), append v to u's list. If the graph is undirected, as with friendships or roads, also append u to v's list, so one edge becomes two entries.
3. Directed edges, such as follows or prerequisites, get only the one entry.

Deciding which of those two cases applies is the actual judgment call, and the problem statement usually implies it rather than saying it.

The build is O(E), and the result answers the neighbors question in O(1). That is why BFS and DFS take adjacency lists rather than raw edge lists as input, since scanning an edge list per node would be O(E) every time.

From edge list to adjacency list

Five undirected edges become ten entries, since every edge is recorded from both of its ends.

from collections import defaultdict

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

for node in sorted(graph):
    print(node, "->", sorted(graph[node]))

Output

A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C', 'E']
E -> ['D']

The two appends in the loop body are the whole algorithm, and the second one is the undirected part.

defaultdict(list) is what keeps it to two lines. With a plain dictionary each append would need a if u not in graph guard first, or a setdefault call.

Checking D confirms the build. It appears in three edges, ("B", "D"), ("C", "D"), and ("D", "E"), and its list holds all three neighbors even though only one of those edges was written with D first.

The sorted calls are only for readable output. Insertion order is what the dictionary actually holds, and no traversal in this unit depends on neighbor order.

One case to watch is an isolated node. A node with no edges never appears in the edge list, so it never appears in the graph either, and problems that count components need the node list supplied separately.

Every edge becomes one-way, so the traversal can only follow edges in whatever direction they happened to be listed.

Each edge is stored from one end only, which quietly turns an undirected graph into an arbitrary directed one. The graph is still valid, just not the graph the problem described.

The visible symptom is undercounting. A DFS from A can report B unreachable even though the input contains the edge (B, A), and a component count comes out too high.

The reason it survives review is that small tests often pass. If the edges happen to be listed in a friendly direction, the traversal reaches everything anyway, and the bug only appears on hidden tests with a different edge order.

So check that line first when a graph solution undercounts. The counting logic usually gets the blame, and the build step is usually the culprit.

DFS without recursion

Recursive DFS borrows Python's call stack, and Python caps that stack at about 1,000 frames. Past it comes a RecursionError, and the cap exists to catch runaway recursion before it exhausts memory.

A path-shaped graph with 10,000 nodes goes 10,000 calls deep and hits that cap, even though the algorithm is perfectly correct.

The fix is to manage the stack yourself. Keep a plain list, push the start node, then loop: pop a node and push its unseen neighbors.

list.append and list.pop are the push and pop from Data Structures, and a list on the heap can hold millions of entries where the call stack held a thousand.

The behavior is unchanged. Same visited-set rule, same O(V + E) cost, and still depth-first, since the most recently discovered node is always the next one explored.

One detail differs from the recursive version. Neighbors come off the stack in reverse order of pushing, so the traversal order is a mirror of what recursion produces, which matters only if the problem cares about order.

This skeleton is also one swap away from BFS. Replacing the stack's pop-from-the-end with a queue's pop-from-the-front flips the traversal from deepest-first to nearest-first, and nothing else changes.

reachable, with an explicit stack

Every node reachable from a start, with no recursion.

def reachable(graph, start):
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)
    return seen

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
    "E": ["F"],
    "F": ["E"],
}
print(sorted(reachable(graph, "A")))
print(sorted(reachable(graph, "E")))

Output

['A', 'B', 'C', 'D']
['E', 'F']

stack.pop() with no argument removes from the end, which is the O(1) operation and the reason this is depth-first. Using pop(0) would make it a slow BFS by accident.

Neighbors are added to seen at push time rather than at pop time, and that ordering matters. Marking at pop time lets the same node get pushed twice from two different neighbors, which wastes work and can multiply the stack size.

The guard sits before the push for the same reason, so nothing already discovered ever enters the stack.

The start node is in seen from the beginning, which is what stops the traversal from coming back to it through the ("B", "A") direction of the undirected edges.

The two clusters give different answers, and that is the point of the test graph. Reachability is per-component, so a traversal from A can never see E or F no matter how it is written.

There are 18 entries, since 9 edges each contribute two appends.

Each undirected edge is recorded from both ends, once in u's list and once in v's, so the total length of all the adjacency lists is 2E.

That is also the answer to a question people ask about the notation. Traversal cost is written O(V + E) rather than O(V + 2E) because constant factors drop, and 2E is what the code actually walks.

The V term is separate and necessary. A graph can have many nodes and no edges at all, and the traversal still has to account for each node.

For a directed graph the same count is just E, since each edge appears once. The distinction rarely changes the Big-O, and it does change the memory estimate when the graph is large.