Representing Graphs

Here is a sample graph that we will use in our examples. Note that this graph is directed and weighted.

Recall that, as with our other data structures, we have two ways to represent a graph: using arrays or using a linked structure.

Adjacency Matrix

In the adjacency matrix we have two arrays. One is an array of graph vertices. Each vertex has a field to hold a reference to the object which is contained in that vertex. The subscript of each vertex is used to store the edges for that vertex in the 2D array which holds the edge information.

The 2D array is the actual adjacency matrix which contains all of the edges. Each row subscript is the subscript of the originating vertex. Each column subscript is the subscript of the destination vertex. These subscripts are defined by the positions of the vertices in the vertex array described above.

If the graph is undirected, then each edge is entered twice. An edge (a,b) is entered as a -> b and b -> a.

If the graph is unweighted, then the adjacency matrix entries are 0 (edge doesn't exist) and 1 (edge exists). If the graph is weighted, then the entry for an edge is the weight of the edge.

The order of the vertices in the array is not specified in any way; it depends on the order in which the vertices are entered.

Adjacency List

The linked representation for graphs is called the adjacency list. In this representation we have a list of vertices. Each vertex has a list of the edges that originate at that vertex. In terms of Java this means that we need two classes: one for the node that holds a vertex, and one for the node that holds an edge.

The node for a vertex needs fields for the following:

• the object that is stored in the vertex
• a reference to the next vertex
• a reference to the edges coming from the vertex
• a mark field that we will use in graph traversal, to keep track of whether we have visited the vertex

The node for an edge needs fields for the following:

• a reference to the vertex to which the edge points (we know which vertex the edge comes from, because the edge is on that vertex's edge list)
• a reference to the next edge coming from the vertex

As in the adjacency matrix the order of the vertices and edges in the lists is not specified in any way; it depends on the order in which the vertices and edges are entered.

Practice

Given the following weighted directed graph, draw the adjacency matrix and the adjacency list.

The images in this handout are taken from our textbook.

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page