Learning About the Graph Construct using Games, Part 1 - Representing a Graph

(Page 2 of 7 )

We are going to explain here the two most famous and most widely used representations: the adjacency matrix method, and the adjacency list method.

Adjacency Matrix Representation

The first representation we are going to discuss is quite straightforward. The graph could be represented by just one two-dimensional array. How? We use a two-dimensional array whose dimensions are n*n, where n is the number of nodes in the graph. Each entry in the array says whether there is an edge between those two nodes or not.

For example, look at the following simple graph:

 

Fig 2. This small graph…

It would be represented by the following array: 

Fig 2b. … is represented by this matrix

Notice that the array dimensions are 4*4, which is the number of nodes in the graph.

Notice also that the second row “1 0 1 0” indicates that node two  is connected to nodes one and three, but not connected to node four or to itself. The other rows can be interpreted easily the same way. Notice that first row is all zeroes, since node one doesn’t point to any other nodes. I hope you are starting to get the idea.

What are the advantages of this representation? It is a pretty attractive representation, with have the following advantages:

1. It is a simple and really easy to comprehend representation.
   
2. It is really easy to answer the question, “does a link exist between nodes A and B” (you need to just look up the entry of row A, column B).
   
3. Some questions such as “Which nodes link to a certain node A?” are easier to answer than with other representations.

Now, what is wrong with this representation? Sadly, there are two main bad points about this representation.

1. If the graph doesn’t have a lot of edges, the array representation wastes a lot of memory. For example, for a 100 node graph with 150 edges, we will end up with an array taking up 10,000 numbers, with only 150 of them being used.
   
2. If you are asked “Which edges are coming out of a certain node A?”, you have to go over the entire A row to answer this question. In other words, in a 1,000 node graph, if node A is only connected to node B, you still must check all 1000 entries in the row of node A to discover this. This can be a serious waste of time.

To put it in another way, the array representation has serious problems when graphs are not very dense. On the other hand, if the graph is dense enough, this representation is very strong, and should definitely be used.

What if the graph is not dense enough? For this case, we have the adjacency list representation.

Next: Adjacency List 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!