Graphs & representations

Towns joined by roads, people who follow each other, courses that require other courses, web pages that link to pages: each is a set of things and the connections between them. That shape is a graph: the things are its nodes (also called vertices), the connections its edges.

Three questions describe any graph:

• Do links have a direction? A road usually runs both ways: that is an undirected graph. "A follows B" doesn't mean B follows A: that is a directed graph, drawn with arrows.
• Do links carry a number? Road lengths, flight prices or delays make a weighted graph; the number on a link is its weight.
• How many links are there? A graph with n nodes can have up to about n² links. Most real graphs, such as road maps and social networks, have far fewer: they are sparse graphs. A graph close to the maximum is a dense graph.

Arrays, linked lists and trees are all special graphs. A graph is what you get when you drop their rules: any node may link to any other, links can form loops, and there may be no single starting point.

Problems usually hand you the links as a list of pairs, an edge list. It is compact, but to find one node's neighbors you would scan every pair. So the first step of almost every graph solution is to turn it into an adjacency list: for each node, the list of nodes it links to.

In an undirected graph each link goes into two lists, once at each end. Watch five roads become five lists:

Reading a node's neighbors is now a walk down its own list, and the whole structure takes O(n + m) space for n nodes and m links. In code it is a list of lists when nodes are numbered from 0, or a map from node to list when they have names.

The in-degree of a node in a directed graph is the number of links pointing into it; its out-degree is the number pointing out. In an undirected graph there is just one count per node, the number of links touching it.

Many problems are only degree counting in disguise. Here a judge is someone trusted by everyone else and trusting no one: in-degree n − 1, out-degree 0. One pass over the pairs fills both counts:

No node was ever visited by following links. Degrees also answer "who has no prerequisites?" (in-degree 0) and "where does every route end?" (out-degree 0), and in-degree is the core of Topological sort.

An adjacency matrix is an n × n grid: the cell in row u, column v is 1 when u links to v, and 0 otherwise (or the weight, in a weighted graph). An undirected graph's matrix is symmetric, because each link sets two cells.

Its strength is the yes-or-no question. With a list, checking whether u and v are linked means scanning u's list; with a matrix it is one cell. This problem asks it for every pair of cities: the rank of a pair is the two degrees added up, minus one when a road joins them, since that road was counted for both.

The best pair, cities 0 and 1, isn't even linked: both have three roads and none is shared. The price of the matrix is its size: O(n²) memory even when there are few links, and O(n) to list one node's neighbors, because the whole row must be read.

Graphs also hide in problems that never say the word. A board of cells is a graph whose neighbors are the cells next door; words that differ by one letter, or states of a puzzle one move apart, are graphs whose links you compute on the fly instead of storing. The next pages explore all of these.