BFS and DFS: Traversal as Problem-Solving

Graphs are everywhere — social networks, dependency graphs, file systems, game maps, call graphs. The traversal is always the same; the difference is the queue vs the stack, which changes the order you visit.

BFS: level by level

def bfs(start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()          # FIFO — process in order of discovery
        for neighbor in node.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS visits nodes in order of distance from the start — shortest path in an unweighted graph, "how many hops," level-order traversal. The queue makes it breadth-first.

DFS: go deep, then backtrack

def dfs(node, visited=None):
    if node in visited: return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

DFS dives deep before backtracking — used for detecting cycles, topological sort, connected components, maze solving, anything where "is it reachable" matters more than "how far." The recursion (or explicit stack) makes it depth-first.

Choosing between them

• Shortest path, level-order, nearest neighbor → BFS.
• Cycle detection, topological order, "does a path exist" → DFS (easier recursion, less memory).
• Either works for "is it connected" — pick the one that's simpler for the graph shape.

Field notes

• visited is non-negotiable — a graph with cycles will loop forever without it.
• Implicit graphs — a grid where neighbors are [(r+1,c),(r-1,c),(r,c+1),(r,c-1)] — are still graphs; the same BFS/DFS works on a board game as on a social network.
• set vs list for visited matters — list makes in O(n); set is O(1).