BFS and DFS

Question¶

Define BFS and DFS and provide an implementation in Python.

BFS¶

Definition
- Explore level by level using queue.
Key trick
- First time you reach a node in unweighted graph gives shortest path length.
Trap
- Mark visited when enqueuing, not when dequeuing, to avoid duplicates.
Use
- Shortest path in unweighted graphs, level order, nearest target.
Complexity
- Time \(O(V + E)\)
- Space \(O(V)\)

DFS¶

Definition
- Explore deeply first using recursion or stack.
Key trick
- Great for structure problems: connected components, cycle detection, topological sort.
Trap
- Recursion depth on deep graphs; forgetting visited causes infinite loops.
Use
- Reachability, backtracking, components.
Complexity
- Time \(O(V + E)\)
- Space \(O(V)\)

Idiomatic Python¶

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    q = deque([start])

    while q:
        node = q.popleft()
        order.append(node)
        for nei in graph.get(node, []):
            if nei not in visited:
                visited.add(nei)
                q.append(nei)

    return order

def dfs(graph, start):
    visited = set()
    order = []

    def go(node):
        visited.add(node)
        order.append(node)
        for nei in graph.get(node, []):
            if nei not in visited:
                go(nei)

    go(start)
    return order

Pytest¶

import pytest

@pytest.mark.parametrize(
    "graph, start, expected_bfs, expected_dfs",
    [
        (
            {"A": ["B", "C"], "B": ["D"], "C": [], "D": []},
            "A",
            ["A", "B", "C", "D"],
            ["A", "B", "D", "C"],
        ),
        (
            {1: [2], 2: [3], 3: []},
            1,
            [1, 2, 3],
            [1, 2, 3],
        ),
    ],
)
def test_bfs_dfs(graph, start, expected_bfs, expected_dfs):
    assert bfs(graph, start) == expected_bfs
    assert dfs(graph, start) == expected_dfs