Graph introduction

Graphs

A graph is the most general way to model "things and the connections between them." Nodes (also called vertices) are the things; edges are the connections. Social networks, road maps, course prerequisites, web links — all graphs.

Trees and linked lists are just special, restricted graphs. Once you can traverse a graph, you can traverse anything.

Directed vs undirected

In an undirected graph, an edge between a and b goes both ways — they're mutual neighbours.
In a directed graph, an edge a → b is one-way; a points to b, but not necessarily back.

Representing a graph: the adjacency list

The workhorse representation is an adjacency list — a map from each node to the list of nodes it connects to:

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

This says a → b, a → c, b → d. To build an undirected graph from a list of edges, add both directions for each edge:

for each [u, v] in edges:
    graph[u].append(v)
    graph[v].append(u)

Grids are graphs too

A 2-D grid is a graph in disguise: each cell is a node, and its neighbours are the cells up, down, left, and right. Several problems in this section are grids — the same traversal ideas apply, you just compute neighbours from (row, col) instead of looking them up in a map.

In this section, adjacency-style problems give edges as a,b pairs, and grid problems give rows of characters separated by |. The next lesson covers how to walk a graph without getting stuck.