Graphs and adjacency lists

Many problems are really about things connected to other things. People in a social network are connected by friendships. Cities are connected by roads. Pages are connected by links. All of these are graphs: a set of verticesvertexA single node in a graph; the thing that edges connect.In the glossary (the things) and edgesedgeA connection between two vertices in a graph, sometimes carrying a weight.In the glossary (the connections between them).

Vertices and edges

Number the vertices from 0 to N − 1. If you can travel both ways along an edge, the graph is undirected; a social network is usually like this, since a friendship goes both ways. If an edge only lets you travel one direction, the graph is directed, the way a one-way street does.

An edge can also carry a weight, a number attached to it, such as a distance on a map or a closeness score in a social network. This lesson sticks to unweighted graphs, where every edge counts the same.

Adjacency list representation

An adjacency listadjacency listA way to store a graph as a list or dictionary that maps each vertex to the list of its neighbours.In the glossary is a dictionary where each vertex maps to a list of its neighbours.

1graph = {2    0: [1, 2],3    1: [0, 2],4    2: [0, 1, 3],5    3: [2]6}

Vertex 0 connects to 1 and 2, vertex 1 connects to 0 and 2, and so on. For an undirected graph, every edge appears twice: reading an edge between A and B means storing B in A's list and A in B's list.

An adjacency list uses space proportional to the number of vertices plus the number of edges, so it stays small on a sparse graph, one where most vertices only connect to a few others. That covers most graphs you will meet in a contest.

Building an adjacency list from input

Suppose the input gives the number of vertices and edges, followed by one edge per line:

14 320 131 242 3

That is 4 vertices and 3 edges, connecting 0-1, 1-2 and 2-3 in a line.

1n, m = map(int, input().split())2graph = {i: [] for i in range(n)}3
4for _ in range(m):5    a, b = map(int, input().split())6    graph[a].append(b)7    graph[b].append(a)8
9for vertex in range(n):10    print(f"{vertex}: {graph[vertex]}")

4 3
0 1
1 2
2 3

0: [1]
1: [0, 2]
2: [1, 3]
3: [2]

The program starts every vertex with an empty list, then reads each edge and adds the neighbour to both lists, since the graph is undirected. The printed result confirms it: vertex 0 only lists [1], since it has one edge, while vertex 1 sits in the middle of the line and lists both [0, 2].

Iterating over neighbours

Once the graph is built, exploring it means looping over a vertex's list.

1graph = {2    0: [1, 2],3    1: [0, 2],4    2: [0, 1, 3],5    3: [2]6}7current = 08for neighbor in graph[current]:9    print(f"Vertex {current} connects to {neighbor}")

This loop is the piece every graph search is built from. BFS and DFS both start at a vertex, look at every neighbour in its list, and repeat from each new vertex they discover. Everything past this lesson builds on being able to ask "what does this vertex connect to?" quickly, which is exactly what the adjacency list gives you.

Adjacency matrix versus adjacency list

An adjacency matrix represents the same information as a 2D grid, where matrix[i][j] is true exactly when an edge connects i and j.

1matrix = [2    [False, True, True, False],3    [True, False, True, False],4    [True, True, False, True],5    [False, False, True, False]6]

A matrix answers "does this edge exist?" instantly, in one lookup, but it always uses space proportional to the square of the vertex count, no matter how many edges actually exist. With 1,000 vertices and only 2,000 edges, the matrix has a million cells for 2,000 real connections. An adjacency list uses space proportional to the edges you actually have, which is why it is the default choice unless a problem specifically needs fast edge-existence checks on a small, dense graph.

Recognizing a graph in disguise

The hard part of graph problems is rarely the code, it is noticing that a problem is a graph problem at all. A set of tasks where some depend on others is a graph: vertices are tasks, and an edge points from a dependency to the task waiting on it. Finding a valid order to do them is a search over that graph.

A maze is the same idea with a different name. Each room is a vertex, each passage between rooms is an edge, and finding a way out is a graph search from your starting room. A flight timetable fits the same shape: each city is a vertex, and each flight is a directed edge from its origin to its destination. Asking whether you can fly from one city to another is asking whether a path exists between two vertices, and the departure times can be ignored entirely for that question.

None of these problems mention the word "graph." Once you notice vertices and edges hiding underneath tasks, rooms or flights, building the adjacency list and running a standard search over it is the same routine every time.

Getting these details right

The most common slip is adding only one direction of an undirected edge. Reading an edge between 0 and 1 and storing only 1 in vertex 0's list loses the fact that 0 is also a neighbour of 1; for an undirected graph, every edge needs both directions stored.

The input's numbering is another place to check carefully. Some problems number vertices 1 through N instead of 0 through N − 1. Read the first example before you write any code, and if the input starts at 1, subtract 1 from every vertex you read so your 0-indexed adjacency list lines up.

And pick the container to match the graph. A dictionary of lists, like the one above, is the right default. If the vertices are a small, dense range, such as 0 to 999 with no gaps, a plain list of lists works too and avoids the overhead of a dictionary; but if the vertex numbers are large and sparse, a dictionary is the one that will not waste memory on vertices that never appear.