Graphs: Everything Is Connected

Why graphs exist

You want to find the fastest route from your apartment to the airport. You could model this as an array of addresses, but then what? The relationships — which roads connect which intersections, how long each road takes — are the whole point. A list can't capture that. A tree could get close, but roads have cycles (you can drive in circles), multiple routes between the same two points, and no obvious root.

That's the moment you need a graph.

A graph G is just a pair (V, E): a set of vertices (nodes) and a set of edges (connections). An edge connects two vertices. That's the whole definition. Everything else — direction, weights, cycles, disconnected components — is a flavor on top.

flowchart LR
    A(["San Francisco"]) -->|"40 min"| B(["Oakland"])
    A -->|"65 min"| C(["San Jose"])
    B -->|"30 min"| C
    C -->|"90 min"| D(["Fresno"])
    B -->|"20 min"| E(["Berkeley"])
    style A fill:#7c5cff,color:#fff
    style D fill:#00ff9d,color:#0a0a0f

Those cities are vertices. The roads between them are edges. The travel times are weights. This is a directed, weighted graph — each edge has both a direction (A→B is not the same as B→A in a one-way street) and a cost.

Strip out the weights and you get an unweighted graph — useful for "can I get there at all?" and "what's the fewest hops?" questions. Strip out the direction and you get an undirected graph — a friendship is undirected (if Alice knows Bob, Bob knows Alice).

Those two axes — directed vs. undirected, weighted vs. unweighted — define which algorithms apply. Get them right first.

Representing a graph in memory

You have two realistic options. Neither is obviously best; it depends on the shape of your graph.

Adjacency list

Each node maps to the list of nodes it connects to. That's it.

# Undirected graph: 5 nodes, 5 edges
graph = {
    0: [1, 4],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2, 4],
    4: [0, 3],
}

Space: O(V + E) — you store every vertex once, every edge twice (once for each endpoint in an undirected graph). If you have 1 million users and each has 200 friends on average, that's 200 million entries, not 1 trillion. That matters.

Iterating a node's neighbors is O(degree) — fast. Checking whether a specific edge exists means scanning the neighbor list — O(degree), not O(1). For most traversal problems that's fine.

This is your default. Almost every graph problem you'll encounter in practice and in interviews uses an adjacency list.

Adjacency matrix

A V×V boolean grid where matrix[i][j] = True means there's an edge from i to j.

# Same 5-node graph as a matrix
matrix = [
    [0, 1, 0, 0, 1],  # node 0's connections
    [1, 0, 1, 1, 0],  # node 1's connections
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [1, 0, 0, 1, 0],
]

Edge lookup is O(1): matrix[i][j] is one array access. But space is O(V²). For a social network with 100 million users, that's 10 quadrillion entries. Not happening. You use adjacency matrices when V is small (say, under a few thousand) and you need fast edge lookups, or when the graph is dense — almost every pair of nodes has an edge.

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Check if edge exists	O(degree)	O(1)
Iterate neighbors of node	O(degree)	O(V)
Best for	sparse graphs	dense graphs, small V

In interviews, unless the problem says "dense graph" or you need O(1) edge lookup constantly, build the adjacency list.

Traversal: how you actually use a graph

Building a graph is table stakes. The interesting part is walking it. Two strategies, both fundamental:

BFS: search in rings

Breadth-first search explores the graph in layers. Start at a source node. Visit all its neighbors. Then visit all their neighbors. Then theirs. You expand like a ripple in a pond.

The data structure that makes this work is a queue — first in, first out. You enqueue neighbors as you discover them and process them in the order they were found, which guarantees you always finish the closer nodes before the farther ones.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node)                       # process it

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)     # mark BEFORE enqueuing
                queue.append(neighbor)

Two things worth burning into memory:

1. Mark visited when you enqueue, not when you dequeue. If you wait until dequeue, the same node can be added to the queue multiple times before it's processed. On a dense graph, that blows up your time complexity.

2. BFS gives you shortest paths for free in an unweighted graph. The first time BFS reaches a node, it did so via the fewest possible edges. That's why navigation apps use BFS-adjacent algorithms — they need "shortest path," not "deepest exploration."

Want "how many hops from A to B?" Run BFS from A, track the hop count per level, stop when you hit B.

DFS: search in depth

Depth-first search picks a direction and commits, going as deep as possible before backtracking. It is recursive by nature (or you simulate recursion with an explicit stack).

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    print(node)                           # process it

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

DFS is the right tool when you need to:

• Detect whether a cycle exists
• Find all connected components
• Check if a path exists between two nodes (you don't need the shortest one)
• Do a topological sort (ordering tasks so dependencies come first)

It's also the skeleton of many grid problems. A 2D grid where you can move up/down/left/right is just a graph where each cell is a node and its neighbors are the adjacent cells. DFS/BFS on a grid is the same algorithm, different indexing.

{ "type": "graph", "title": "BFS vs DFS traversal order" }

Step through both traversals on this graph and watch the order nodes get visited. BFS fans out one layer at a time; DFS goes all the way down one path before touching another. Neither is "better" — they answer different questions.

The visited set: not optional

On a tree, you can't revisit a node because there's only one path to each node. Graphs don't have that property. Without a visited set, DFS on a graph with cycles loops forever. BFS enqueues the same node hundreds of times. Both end in a hang or an OOM error.

This is the most common graph bug beginners write. The fix is always the same: keep a visited set, check it before processing, update it immediately.

Putting it together: connected components

Here's a complete problem to make traversal concrete. Given an undirected graph, count how many connected components it has (i.e., how many separate "islands" of nodes exist, with no edges between islands).

def count_components(n, edges):
    # Build adjacency list
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    components = 0

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    for node in range(n):
        if node not in visited:
            dfs(node)        # kicks off a full DFS from this unvisited node
            components += 1  # every new DFS root is a new island

    return components

Walk through what happens: you iterate every node. If it's unvisited, you start a DFS from it — which will visit every node reachable from it, marking them all as visited. When the DFS finishes, you've fully explored one component. The outer loop finds the next unvisited node (a different component) and repeats. Count how many times you had to start a fresh DFS and that's your answer.

Time complexity: O(V + E). You visit every vertex once and traverse every edge once (twice, once from each end, but constants don't count). Space: O(V) for the visited set and the DFS call stack in the worst case.

Directed graphs and one-way streets

In an undirected graph, every edge goes both ways, so you add it to both adjacency lists. In a directed graph, an edge from u to v only goes u→v:

# Directed graph — add edge only in one direction
graph[u].append(v)   # u can reach v
# graph[v].append(u) — this line does NOT exist

This changes everything about reachability. Just because you can get from A to B doesn't mean you can get back. Twitter's follow graph is directed: you following someone doesn't mean they follow you. Task dependency graphs are directed: "compile before link" is not reversible.

When you see a problem involving ordering, scheduling, or dependency resolution, you're almost certainly looking at a directed acyclic graph (DAG) — a directed graph with no cycles. The signature algorithm for DAGs is topological sort, which the full graph structure page covers in depth.

What BFS and DFS unlock

These two traversals are primitives that other algorithms are built on:

• Shortest path (unweighted) → BFS directly. Dijkstra's for weighted.
• Cycle detection → DFS. Track a "currently on the stack" set alongside visited.
• Topological sort → DFS with a finish-order stack, or BFS using in-degree counts (Kahn's algorithm).
• Bipartite check → BFS, coloring nodes alternately and checking for conflicts.
• Connected components / islands → DFS or BFS, as shown above.
• Flood fill → BFS on a grid. The algorithm underneath the paint bucket tool.

The BFS patterns page walks through the queue-based patterns in detail — matrix problems, multi-source BFS, 0-1 BFS. Once you have the fundamentals here locked, that's where to go next.

Gotchas people actually hit

Forgetting that the graph might be disconnected. BFS or DFS from a single source won't visit all nodes if some are in separate components. If you need to process the whole graph, wrap your traversal in a loop over all nodes (like the connected-components example above).

Building a directed graph when you need undirected (or vice versa). If you add graph[u].append(v) but forget graph[v].append(u) on an undirected problem, you'll get wrong answers that look almost right. Double-check the edge-building step first when something's off.

Stack overflow on large graphs with recursive DFS. Python's default recursion limit is 1000. A graph with 100,000 nodes where DFS goes deep will crash. Either increase the limit (sys.setrecursionlimit), or rewrite DFS iteratively with an explicit stack. BFS never has this problem because it uses a queue, not recursion.

Assuming nodes are numbered 0 to n-1. Real-world graph problems often use strings as node IDs (city names, user IDs). Your adjacency list needs to be a dict, not a list, in that case. Not a bug that crashes — just one that silently gives you wrong answers or key errors.

Where to go from here

This lesson gave you the skeleton: what a graph is, how to store one, and how to walk it. That's enough to solve a surprising number of problems.

The natural next steps:

• Graph structure deep-dive — weighted graphs, Dijkstra's algorithm, topological sort, union-find for connected components.
• BFS patterns — multi-source BFS, 0-1 BFS, BFS on implicit graphs. The queue pattern shows up in more places than you'd expect.
• Trees revisited — a binary search tree is a graph with exactly one path between any two nodes and a root. Every tree algorithm is a restricted graph algorithm. Once you see that, the relationship between the two makes sense.

The graph is the data structure that earns its keep in hard interview problems. Most medium-to-hard LeetCode problems are either graphs in disguise or explicitly labeled as such. Get comfortable with the adjacency list and BFS/DFS and you'll have tools for the bulk of them.