Learning About the Graph Construct using Games, Part 1 - Adjacency List Representation

(Page 3 of 7 )

The adjacency list method is a different representation that is quite good when graphs are not dense enough. How does it work? This is simple. All it does is store a series of linked lists, one linked list per node. Each linked list stores the edges coming out of a certain node.

In other words, the first linked list stores the ids of all nodes node 1 is connected to. The second linked list stores the ids of all nodes node 2 is connected to, and so on. Fir example, if we look at the following graph: 
 

Fig 3. This graph…

It would be represented that way:

 

Fig 3b. … is represented by this adjacency list.

Notice that the number of linked lists is equal to the number of nodes. The first linked list is empty, since node one is not connected to anything. The second linked list has two elements, since node two is connected to both node one and node three. We are basically using an array of linked lists. I hope this expression doesn’t scare you. It is simpler than it sounds.

What are the advantages of this representations?

1. If the graph is not very dense, this representation is great, because it doesn’t waste memory locations for non-existent edges.
   
2. It is easy to list all of the edges coming out of a node. The time taken is exactly equal to the number of edges, unlike what happens when using adjacency matrices.

What are the disadvantages?

1. If the graph is very dense, (for example, we have a fully connected graph), the memory taken is more than that taken by adjacency matrices, because of the extra allocation for the pointers in the linked list.
   
2. To answer the question “Does an edge exist between nodes A and B?”, you must visit all nodes of the linked list of A (as opposed to looking up one entry when using adjacency matrix).

The bottom line is, adjacency lists shine when graphs are not very dense. On the other hand, an adjacency matrix is great when graphs are very dense.

This is going to be the last bit of theory, before we jump straight into the first game.

Before we drift away from the topic of representation, I want to quickly touch on a very important point. It is about important variations.

Next: Variations on graph representation >>
 

More Development Cycles Articles
More By Mohamed Saad

Comments On: Learning About the Graph Construct using Games, Part 1

>>> Be the FIRST to comment on this article!