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