BFS vs DFS: Picking the Right Frontier

Graph traversal is one algorithm with one moving part: the data structure that holds the frontier.

• A queue gives you breadth-first search.
• A stack gives you depth-first search.

That's the only difference. Same code, different container.

from collections import deque

def bfs(graph, start):
    seen = {start}
    frontier = deque([start])
    while frontier:
        node = frontier.popleft()       # FIFO — earliest added node first
        yield node
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                frontier.append(nxt)

def dfs(graph, start):
    seen = {start}
    frontier = [start]
    while frontier:
        node = frontier.pop()           # LIFO — most recently added node first
        yield node
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                frontier.append(nxt)

When to use which

BFS finds the shortest path in unweighted graphs. The first time you reach a node, you've reached it by the fewest edges. That's because nodes are dequeued in order of their distance from the start.

DFS is what you want when you're searching for any path, detecting cycles, doing a topological sort, or exploring a state space where you want to commit deep before backtracking. DFS pairs naturally with recursion, but the iterative version above is bug-free even when the graph is huge enough to blow your call stack.

The seen-set is not optional

Forgetting seen turns either algorithm into a non-terminating disaster on any graph with a cycle (i.e., almost all real graphs). Always:

1. Mark start seen before putting it in the frontier.
2. Mark a neighbor seen at the moment you add it to the frontier, not when you dequeue it. Otherwise you'll add the same node multiple times before processing it.

Cost

Both are O(V + E). They visit each vertex once and each edge at most twice (once from each endpoint, in undirected graphs). Memory is O(V) for seen plus the size of the frontier.