Graphs — BFS & DFS (Breadth-First Search & Depth-First Search)

What Is a Graph?

Formally, a graph G = (V, E) is a pair of two sets: V (a set of vertices / nodes) and E (a set of edges / connections). That is the entire definition. Everything else is built on top of it.

Types of Graphs — A Visual Reference

Graphs come in many flavours. The type of graph determines which algorithms you can use and what guarantees they provide. Misidentifying your graph type is the #1 source of algorithm bugs.

Graph Vocabulary — Every Term You'll Encounter

Representing Graphs in Python

Before you can run BFS or DFS, you need to store the graph in memory. The two main approaches — adjacency list and adjacency matrix — have wildly different performance characteristics.

# ══════════════════════════════════════════════════════════════
# METHOD 1 — Adjacency List (dict of lists)  ← use this 99% of time
# ══════════════════════════════════════════════════════════════

# Undirected graph:  A—B, A—C, B—D, C—D, D—E
undirected = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D'],
}

# Directed graph:  A→B, A→C, B→D, C→D
directed = {
    'A': ['B', 'C'],   # A points TO B and C
    'B': ['D'],         # B points TO D only
    'C': ['D'],
    'D': [],             # D has no outgoing edges
}

# Weighted graph: edge (A,B) has weight 4, (A,C) has weight 7
weighted = {
    'A': [('B', 4), ('C', 7)],
    'B': [('A', 4), ('D', 2)],
    'C': [('A', 7), ('D', 9)],
    'D': [('B', 2), ('C', 9)],
}

# ══════════════════════════════════════════════════════════════
# METHOD 2 — Adjacency Matrix (2D list)  ← use for dense graphs
# ══════════════════════════════════════════════════════════════
# Nodes indexed: A=0, B=1, C=2, D=3
# matrix[i][j] = 1 if edge (i,j) exists, else 0
matrix = [
    [0, 1, 1, 0],  # A: connected to B, C
    [1, 0, 0, 1],  # B: connected to A, D
    [1, 0, 0, 1],  # C: connected to A, D
    [0, 1, 1, 0],  # D: connected to B, C
]

# ── Helper: build graph from edge list (common in interviews) ──
def build_graph(n, edges, directed=False):
    """Build adjacency list from edge list.
    n: number of nodes (0-indexed)
    edges: list of [u, v] pairs
    """
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)  # add reverse for undirected
    return graph

# Usage:
g = build_graph(5, [[0,1],[0,2],[1,3],[2,3],[3,4]])
print(g)
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}

The Story That Explains Graph Traversal

BFS and DFS are the two fundamental algorithms for visiting every node in a graph — the backbone of hundreds of real-world applications. Both run in O(V + E) time. The difference is entirely in their order of exploration — which comes down to one data structure choice: queue vs stack.

Live Animation — BFS vs DFS on the Same Graph

Watch BFS sweep level-by-level and DFS dive deep before backtracking — on the identical 9-node graph. Press Step → to go one node at a time, or Auto Play to watch the full traversal.

BFS — Breadth-First Search

BFS uses a queue (FIFO). When you visit a node, you enqueue all its unvisited neighbours. Because the queue processes nodes in the order they were discovered, you always finish all nodes at distance d before visiting any node at distance d+1.

from collections import deque

def bfs(graph: dict, start) -> list:
    """
    Breadth-First Search — returns nodes in visit order.
    graph: adjacency list {node: [neighbour, ...]}
    """
    visited = {start}           # mark on ENQUEUE, not dequeue
    queue   = deque([start])   # O(1) popleft — critical!
    order   = []

    while queue:
        node = queue.popleft()    # FIFO — front of queue
        order.append(node)

        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)  # enqueue at BACK

    return order

graph = {'A':['B','C'],'B':['A','D','E'],'C':['A','F','G'],'D':['B','H'],'E':['B','H'],'F':['C','I'],'G':['C','I'],'H':['D','E'],'I':['F','G']}
print("BFS order:", " → ".join(bfs(graph, 'A')))

BFS Superpower — Shortest Path on Unweighted Graphs

BFS guarantees the shortest path (fewest hops) between two nodes on an unweighted graph, because it explores all paths of length 1 before length 2, and so on. This is the algorithm behind social "degrees of separation", web crawl depth limits, and game pathfinding.

from collections import deque

def bfs_shortest_path(graph, start, end):
    """Returns shortest path list from start→end, or [] if unreachable."""
    if start == end: return [start]
    visited = {start}
    queue = deque([(start, [start])])  # (node, path_so_far)
    while queue:
        node, path = queue.popleft()
        for nb in graph[node]:
            if nb not in visited:
                new_path = path + [nb]
                if nb == end: return new_path  # ← guaranteed shortest
                visited.add(nb)
                queue.append((nb, new_path))
    return []  # unreachable

def bfs_distances(graph, start):
    """Returns dict of shortest distances from start to every node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1  # one hop further
                queue.append(nb)
    return dist

path = bfs_shortest_path(graph, 'A', 'H')
print(f"Shortest path A→H: {' → '.join(path)} ({len(path)-1} hops)")

distances = bfs_distances(graph, 'A')
print("Distances from A:", distances)

DFS — Depth-First Search

DFS uses a stack (LIFO). You push a node, pop it, visit it, and immediately push all its unvisited neighbours. The last pushed neighbour is the next one visited — so you always go deeper before going wider.

# ── Iterative DFS ─────────────────────────────────────────────
def dfs_iterative(graph, start):
    visited = set()
    stack   = [start]
    order   = []
    while stack:
        node = stack.pop()           # LIFO — last in, first out
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in reversed(graph[node]):  # reverse → natural order
            if nb not in visited:
                stack.append(nb)
    return order

# ── Recursive DFS ──────────────────────────────────────────────
def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None: visited = set()
    if order   is None: order   = []
    visited.add(node)
    order.append(node)                # PRE-ORDER: process before recursing
    for nb in graph[node]:
        if nb not in visited:
            dfs_recursive(graph, nb, visited, order)
    return order
    # POST-ORDER: move order.append(node) to HERE (after the for loop)

print("Iterative:", dfs_iterative(graph, 'A'))
print("Recursive:", dfs_recursive(graph, 'A'))

DFS Power Applications

# ══════════════════════════════════════════════════════════════
# 1. CYCLE DETECTION — directed graph
# ══════════════════════════════════════════════════════════════
def has_cycle_directed(graph):
    """True if directed graph contains a cycle (back-edge detection)."""
    visited = set()
    rec_stack = set()   # nodes in CURRENT DFS path

    def dfs(node):
        visited.add(node); rec_stack.add(node)
        for nb in graph.get(node, []):
            if nb not in visited:
                if dfs(nb): return True
            elif nb in rec_stack:
                return True   # back-edge = cycle
        rec_stack.discard(node)
        return False

    return any(dfs(n) for n in graph if n not in visited)

# ══════════════════════════════════════════════════════════════
# 2. TOPOLOGICAL SORT — DFS post-order on a DAG
# ══════════════════════════════════════════════════════════════
def topo_sort(graph):
    """Topological ordering of a DAG using DFS post-order."""
    visited = set()
    result  = []

    def dfs(node):
        visited.add(node)
        for nb in graph.get(node, []):
            if nb not in visited: dfs(nb)
        result.append(node)    # POST-ORDER: after all children

    for node in graph:
        if node not in visited: dfs(node)
    return result[::-1]       # reverse → topological order

# ══════════════════════════════════════════════════════════════
# 3. CONNECTED COMPONENTS
# ══════════════════════════════════════════════════════════════
def connected_components(graph):
    """Returns list of components; each component is a set of nodes."""
    visited    = set()
    components = []

    def dfs(node, component):
        visited.add(node); component.add(node)
        for nb in graph[node]:
            if nb not in visited: dfs(nb, component)

    for node in graph:
        if node not in visited:
            comp = set()
            dfs(node, comp)
            components.append(comp)         # each DFS run = 1 component

    return components

# ── Tests ──
dag = {'A':['C'],'B':['C','D'],'C':['E'],'D':['F'],'E':['F'],'F':[]}
print("Topo sort:", topo_sort(dag))

disc_graph = {'A':['B'],'B':['A'],'C':['D'],'D':['C'],'E':[]}
print("Components:", connected_components(disc_graph))

Animated Code Walkthrough — Line by Line

Step through each algorithm's execution. The highlighted line shows what is running now; the state panel shows every variable at that exact moment.

Time & Space Complexity — Full Comparison

BFS vs DFS — When to Use Which

Real-World Use Cases

Complete Graph Type × Algorithm Reference

Golden Rules