Introduction

A graph is an abstraction representing some objects and connections between pairs of objects. In its simplest form, a graph has just two pieces:

• A set of vertices $V$, representing the objects we are interested in. These could represent, for instance, people, physical locations, webpages, or even other graphs.
• A set of edges $E$, consisting of pairs of the form $(v_i, v_j)$, representing a connection between vertices. These could represent, for instance, relationships between people, roads between physical locations, links between webpages, or isomorphisms between graphs.

More generally, a graph contains information about what pairs of objects are related to each other in some way.

Let us first define some terminology that will make talking about graphs less cumbersome. If $G$ has an edge $e = (u, v)$, we say $u$ and $v$ are adjacent. We also say $u$ is a neighbor of $v$ and $v$ is a neighbor of $u$. The edge $e$ is also referred to as being incident on $u$ (and $v$, as well).

The degree of a node $v$ (denoted $\text{deg}(v)$) is the number of other nodes adjacent to it, or in other words, the number of neighbors it has. Equivalently, $\text{deg}(v)$ is the number of edges incident on $v$.

We define a path as a sequence of nodes such that any two adjacent nodes in the sequence are adjacent in $G$. Two nodes $u$ and $v$ are then reachable from each other if there is a path that starts at $u$ and ends at $v$ (or vice versa).

As with most sufficiently complex mathematical notions, there is an infinite black hole of graph theory terminology, much of which we will see in the future. For now, however, these terms are sufficient for making basic claims about graphs. The following is one of the most important facts about graphs, especially for the purpose of runtime analysis.

The Handshaking Lemma. For any graph $G$, the sum of the degrees of every node is twice the number of edges. That is,

Intuition. It is more useful to consider the edge-incidence definition of degree here. First, observe that every edge is incident on exactly two vertices. Thus, in our sum of degrees, any given edge contributes to exactly two $\text{deg}(v)$ terms by 1. Therefore, we would expect this sum to be equal to twice the number of edges.

Proof. We can formalize this intuitive idea. Let $\delta_{ij} = 1$ if and only if $e_j$ is incident on vertex $v_i$; otherwise, it is defined as 0. So, we can now rewrite $\text{deg}(v_i) = \sum_{j=1}^{m} \delta_{ij}$. So, the sum of all of these degrees is

Here we simply rearrange the sum and use the fact that there are exactly 2 vertices incident on any edge, so $\sum_{i=1}^{n} \delta_{ij} = 2$.

Representations

We have discussed the mathematical idea of a graph, but it remains to define the abstract data type for use in our code:

There are two common ways of implementing this data type.

Adjacency Matrix

One way to interpret a graph is that it is simply a binary relation on the vertices – that is, any two vertices are either adjacent or they aren’t adjacent. This leads to a natural programmatic representation – for every pair of vertices, keep track of whether they are adjacent or not. We can use any data type that acts as a two-place boolean predicate, but the most obvious choice is a two dimensional array. True to the relation interpretation, we could use a two-dimensional boolean array, but for reasons that will make sense later, it is more typical to use an integer array and store a $1$ for adjacency and $0$ for non-adjacency. This array is known as an adjacency matrix.

Adjacency matrices perform one operation very quickly: to detect whether two vertices are connected by an edge, we can simply test whether the adjacency matrix has a 1 in the corresponding position. This can be done with (approximately) two pointer deferences, so this operation takes $\Theta(1)$ time.

Let us investigate the other operations. To iterate over every neighbor of $v_i$, we can iterate through the $i$-th row and report all the entries which are 1. Since a row is size $n$, this always takes $\Theta(n)$ time. Similarly, to iterate over all edges, we can go through the entire matrix and return all of the entries with a 1 in them, taking $\Theta(n^2)$ time. As we will see, neither of these are particularly good – this is because we waste a lot of time iterating over entries which don’t actually represent any edges, but are just empty placeholds for where edges could be. The next representation, the adjacency list, addresses this issue.

Adjacency List

One useful metric of graphs is their density, which is how many edges they have relative to the number of vertices they have. A graph is called dense if its number of edges is asymptotically close to the maximum. A graph is called sparse if it is not dense; that is, if its number of edges is far less than the maximum. Some formalizations of these terms exist (see tangent

In practice, many graphs are sparse. For example, imagine a graph representing locations in the real world. You could imagine a complex enough graph of this type having, say, a million different locations. For any particular location, however, the maximum number of edges between that location and adjacent locations is probably no more than 4 – maybe up to 5, 6, if you have some really crazy intersection. It is certainly nowhere close to a million. We would expect, then, that this graph probably has no more than 5 to 6 million edges, even though it could in principle have up to ${10^6 \choose 2} \approx 10^{12}$ edges.

Sparse graphs benefit from a more efficient representation called an adjacency list. Here, for each vertex, we simply store a “list” of adjacent vertices. I put list in scare quotes since it really makes more sense to think of this as a set (there are no duplicates, nor is there any particular order), but conventionally it’s just called a list anyway.

Comparing the two figures, it should hopefully clear where the speedup comes from: instead of checking every node to see if it is adjacent to some vertex $v_i$, we can just instantly have access to a list of neighbors and iterate over it. So, neighbor iteration for adjacency lists is in $\Theta(\text{deg}(v_i))$. Since there are $\text{deg}(v_i)$ neighbors anyway, this is literally the best we can do. We can also iterate over all edges quickly by iterating every list; this takes $\Theta(n + m)$ time.

On the other hand, edge detection is not as nice. In order to determine if $(u, v) \in E$, we have to go through $u$’s list and check if $v$ is in it, or vice versa. As long as we know the length of each list, we can pick the shortest, so edge detection takes $\Theta(\text{min}(\text{deg}(u), \text{deg(v)}))$. Note that for dense graphs, this can be quite bad… $\Theta(n)$, in the worst case! Much worse than the $\Theta(1)$ we had for adjacency matrices. But in sparse graphs, where we expect the degree to be relatively small, this is still quite efficient.

So, we can see that there is a tradeoff – by using lists, we get faster neighbor and edge iteration, but slower edge detection. By using matrices, we get faster edge detection, but slower neighbor and edge iteration. As it turns out, however, neighbor iteration is used wayyy more than any other operation. This operation is essentially the fundamental operation used when searching through graphs, which is kind of the thing you do with graphs. Hence, adjacency lists are generally used unless there is a good reason in particular to use adjacency matrices.

Searching

So far, we have only answered local questions about graphs:

• What are the neighbors of $v$?
• Are $u$ and $v$ adjacent?

But not yet questions which answer higher level, global properties of graphs. Here is an example:

The reachability problem: Given a graph $G$ and two vertices $u$ and $v$, determine whether there is a path between $u$ and $v$ using edges in $G$.

It is easy to see why this is a practically useful problem to have a solution for.

• If your graph represents a set of locations and roadways between them, this problem asks whether there is a (literal, physical) path between two locations.
• If your graph represents a social network (with vertices as people and edges as personal connections), this problem asks whether there is a line of connections between two people – this would tell you, for instance, whether a rumor could spread between these two people just by word of mouth.
• If your graph represents states and transitions between them, this problem asks whether there is a way to get from one state to another only through transitions.

The most common way to solve the reachability problem is with a searching algorithm. There are many different ways to search a graph, but almost all of them are basic variations of the following high level algorithm.

As it turns out, it’s not much harder to solve a more general problem: which vertices are reachable from $u$? This is the problem searching algorithms actually solve. Here’s how: starting at $u$, we begin building a set $X$ of explored vertices, which we know for sure are reachable from $u$. We repeatedly expand $X$ by finding vertices which are connected to already explored vertices. Eventually, we run out of vertices to add, and we stop – at this point, $X$ contains all of the vertices reachable from $u$!

Let’s try to describe this in a way that is a little closer to an actual algorithm. Let’s say a vertex $v$ is a fringe vertex if $v \not\in X$, but $(u, v) \in E$ for some $u \in X$. Basically, $v$ is a fringe vertex if it hasn’t been explored, but it is one edge away from a vertex that has been explored. Then our algorithm should repeatedly find a fringe vertex and add it to $X$. Algorithm 1 summarizes this approach, and Figure 4 visualizes the idea.

We have left out a lot of details here, but let’s first prove that this high-level algorithm accomplishes our goal before we try to flesh it out.

Theorem. After Algorithm 1 terminates, $X$ contains exactly the vertices in $G$ which are reachable from $u$.

Let’s first prove the following invariant: all vertices in $X$ are reachable from $u$ .This certainly holds before the loop starts ($u$ is reachable from itself), so we just need to show that it holds after each iteration of the loop. We need to show that the new element we’ve added to $X$, the fringe vertex $v$, is reachable from $u$. By definition of fringe vertex, there is some $w \in X$ such that $(w, v) \in E$. By the invariant, $w$ is reachable from $u$, and so there is some path

If we construct a new path by simply appending the edge $(w, v)$, we get the path

and so $v$ is reachable from $u$. Thus, the invariant is preserved.

So, when the algorithm terminates, $X$ contains only vertices rachable from $u$. Aren’t we done, then? Not quite. We have shown that if a vertex is in $X$, it is reachable from $u$, but we still need to show that if a vertex is reachable from $u$, it is in $X$. Essentially, thus far we have only shown that $X$ is a subset of the vertices reachable from $u$, but we need to show it is equal.

This direction is slightly more involved. There are many ways to proceed, but here is one idea: for each vertex $v$ that is $u$-reachable, we can prove the following invariant: $X$ either contains $v$ or there is a fringe vertex $w$ such that there is a path from $u$ to $v$ that passes through $w$.

In other words, the invariant says that we have either found $v$, or we are on our way to finding it through some fringe node $w$. Let us now prove the invariant, again by induction. First, the base case: when $X = \{ u \}$, does this invariant hold? If $u = v$, then the first part of the “or” is clearly true, since $v \in X$. Otherwise, consider any path from $u$ to $v$. Since $u \neq v$, the path consists of more than one path, and so there must be some node $w$ such that $(u, w) \in E$. But since $u$ is the only explored node, $w$ must be a fringe node.

Now, assuming the invariant is true for some iteration, we need to show that it holds for the next as well. Every iteration we add some fringe node $\ell$ to $X$. If $\ell = v$, then clearly the invariant is still true, since now $v \in X$. If $\ell \neq w$, then $w$ is stil a fringe node, and so the second part of the or “or” is still true. The more complicated case is when $\ell = w$. We know there is some path $p = \langle u, \dots, w, w', \dots v \rangle$ that connects $u$ and $v$ and contains $w$. Notice the suspiciously placed $w'$, which is the node after $w$ in the path. Since $p$ is a path, $(w, w') \in E$. After exp

So we’ve shown that the algorithm correctly finds exactly the vertices we need to find. However, we haven’t specified completely how we even find fringe vertices in the first place. Until we do that, we can’t even implement this algorithm, let alone analyze its runtime.

Breadth-first Search

Depth-first Search

Path Reconstruction