Algorithms – Adjacency Lists and Matrices

Nodes can be connected to other nodes – otherwise it would be a bleeding useless graph! :D

But how do we know which node is connected to which nodes? Welcome to the wonderful world of Adjacency Lists and Matrices!

Also, i apologise for the long pause in posts! :(

Adjacency Lists

Adjacency Lists structure views the edge-node relation from both points of view. Because of this we are able to speed up the performance of a number of Graph methods, some of which we shall meet in due time.

For now, consider the following ‘simple’ directed graph of how we could travel from one city to another in a game of World of Warcraft:

Here we have a nice Digraph. In case you’re wondering what it all means, basically we see here that you can travel from Silvermoon and Undercity to Thunderbluff. You can travel from Silvermoon to Orgrimmar and if you felt like it, travel from Thunderbluff to Orgrimmar ;)

Anyway! Back to Adjacency Lists! For the above Digraph, the Adjacency list would look like as follows:

Now with this, we can instantly see which cities have travel path going to one city and coming from another. The best example is Thunderbluff; in which we can see that it has 2 nodes coming into it, and it goes out to 1 node. This means 2 things:

• It has an outdegree of 1
• It has an indegree of 2

Finally, in case one is wondering, the space complexity of an Adjacency List is proportional to the degree of the nodes. Therefore it is O(n+m), where n is the number of nodes and m is the total number of edges. Of course this is the space complexity for all Adjacency lists in a graph; the space complexity of the list for one node would be O(degree(n)), where degree(n) is the total number of IN and OUT edges, such as for Thunderbluff:

• O(degree(Thunderbluff))  =  O(3)     [1 IN + 2 OUT = 3]

 

Adjacency Matrices

This is the final part, and it a little easier to explain :) An Adjacency Matrix is similar to an Adjacency List in that we store which nodes are connected what, but this time we store them in a matrix – or in the simplest sense, a 2-dimensional array.

Because of this, we can now access the adjacencies between 2 nodes in constant time. However, as you may have already guessed, a 2D-Array can use up a lot of memory! Therefore, we are trading space, for time! [the space complexity is O(n^2)]

Once we have our Graph, we number the nodes 0,1, …, n-1, with n being the total number of nodes. Once this is done, we can now draw up at matrix , A, as a 2D-Array of size n x n to represent our graph.

With this, we can say that at index A[i,j] we have stored there a reference to the edge (i,j). That is, the edge (if it exists) between node i and node j.

Now that this is out of the way, let’s have an example!!

 

This time, let us observe the following Graph for Stargate Planets.

As some may have noticed, i have already numbered the nodes 0 – 3. Now we can construct our 4 x 4 Matrix.

Here a ‘1’ represents that node ‘i’ is connected to node ‘j’, where as a ‘0’ represents the fact that no edge exists between them. Remembering that this is a Digraph.

So even though there exists an edge such that we can get from node ‘0’ to node ‘3’, there is no edge that exists that can get us from node ‘3’ to node ‘0’.

 

On another note, if this graph had weighted edges, then the ‘1’s would be replaced by the weights of the edges from node ‘i’ to node ‘j’.