[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Algorithms that work on graphs.

1. Graph definitions

A graph consists of a set of vertices (which we typically take to just be numbered 1 to n), and a set of edges, each of which is a pair of vertices. Graphs may be directed (edges are ordered, so uv and vu are different edges) or undirected (uv and vu are the same edge). Typically we assume that a graph has no parallel edges, (which is why we can refer to an edge by just giving its endpoints).

2. Representation

Two representations are standard: adjacency list form, which is an array of n linked lists, where v appears in A[u] just in case uv is an edge, and adjacency matrix form, where A[u][v] = 1 if uv is an edge and 0 otherwise. Adjacency lists permit fast traversal of outgoing edges from a particular node and are more compact if the graph is sparse. Adjacency matrices permit testing the existence of an edge in O(1) time, as compared to O(V) in the worst case for adjacency lists. More complex data structures (e.g. an array of hash tables) can provide the advantages of both representations.

3. Algorithms that explore graph structure

4. Graph optimization problems


2014-06-17 11:58