Adjacency Lists

(If you aren’t familiar with graph theory, I advise you to read my post on minimum spanning trees, where I define several important graph-theoretic terms that are relevant to this entry.)

There exist several ways to represent a graph. For example, you can represent a graph as an adjacency matrix, as an edge list, or as an adjacency list. In my Python implementation of Kruskal’s algorithm, I used an edge list.

Today I will discuss adjacency lists, because I’m going to use adjacency lists in some algorithms that I will post about soon.

The idea of an adjacency list is very simple. In its most basic form, an adjacency list is just a collection of lists of adjacent vertices. So, if we want to know which vertices are adjacent to a vertex v and our adjacency list is L, then L[v] is the list of vertices adjacent to v.

More precisely, L[v] is the list of vertices that v has an out-edge to. Adjacency lists can represent directed graphs. So, even if u is an element of L[v], v is not necessarily an element of L[u].

If nonnegative integers name the vertices or if we want to create a correspondence between the nonnegative integers and the vertices, then you can very easily implement an adjacency list with an array of arrays. Similarly, you can also implement an adjacency list with an array whose cells point to a linked list of the adjacency vertices.

If nonnegative integers don’t name the vertices and we don’t want to create a correspondence between the nonnegative integers and the vertices, then you can very easily implement an adjacency list with an associative array whose keys are the vertices’ names and whose values are the names of adjacent vertices.

You can implement the adjacency-list representation of a weighted graph with an array of arrays of vertex-weight pairs. For example, consider a weighted directed graph. Vertex #0 has an out-edge of weight 5 to Vertex #1 and an out-edge of weight 10 to Vertex #2, Vertex #1 has an out-edge of weight 15 to Vertex #2, and Vertex #2 has no out-edges. You can represent that graph as {{{1, 5}, {2, 10}}, {{2, 15}}, {}}.

Because an adjacency list takes up only O(V + E) memory, adjacency lists are useful for representing a sparse graph, which is a graph that has much fewer edges than the maximum number of edges.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s