Graphs

Overview

A graph is a set of nodes (vertices) connected by edges, used to model networks like maps, social connections, or dependencies. Edges can be directed or undirected and optionally weighted. A common representation is an adjacency list (a dict mapping each node to its neighbors), which uses O(V + E) space and supports traversals like BFS and DFS in O(V + E) time.

Syntax / Usage

Represent a graph as a dictionary of neighbor lists.

graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a"],
    "d": ["b"],
}

print(graph["a"])          # neighbors of a -> ['b', 'c']

graph.setdefault("e", [])  # add a new node
graph["d"].append("e")     # add an edge d -> e

Examples

Breadth-first search visits nodes level by level using a queue:

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    order = []
    while queue:               # O(V + E)
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(graph[node])
    return order

print(bfs(graph, "a"))  # ['a', 'b', 'c', 'd', 'e']

Depth-first search explores as far as possible using recursion:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)          # O(V + E) overall
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

print(dfs(graph, "a"))  # {'a', 'b', 'c', 'd', 'e'}

Common Mistakes

• Not tracking visited nodes, causing infinite loops on cycles
• Confusing directed and undirected edges when adding connections
• Using a stack for BFS or a queue for DFS by mistake
• Assuming every node is reachable — disconnected graphs exist
• Sharing a mutable default argument for visited across calls

See Also

data-structures-trees data-structures-queues data-structures-hash-tables