Algorithms - More graphs

More Graphs (yay)

Note: This is a direct follow on (or a sequel if you want) to this post, so you might want to read that first!

Representing graphs

So you've seen what graphs are and how they can be classified. But how do you represent them in code? For example, do we put them in an array, a vector or a linked list? There isn't one definite answer, so let's go through some of the methods of representing them.

The representation we use depends on a couple of things, like:

• The graph properties


• What algorithms we are going to use with the graph


• What language we're using


• What the program is actually for

So let's talk about the first way of representing a graph..

Adjacency lists

This is pretty easy. You have a list of all the nodes, and then for each node list all the nodes adjacent to it. If the graph is directed then adjacent means 'the node points to it'.

Here's an example adjacency list using the really simple digraph from the last post:





The table doesn't really need any explanation as it's pretty straightforward! Note that just because there's only one adjacent node (at most) for each node, it doesn't mean you can't have more than one! You can have as many as possible.

Adjacency matrices

So this is another way of representing graphs. You have a 2D array where each dimension is a node of the graph. If there is an edge from A to B, then you enter 1 into the matrix, and 0 if there isn't. It sounds a lot harder than it is! Here's an example of one using the graph from above:



You can see that there are 3 edges in the digraph, and 3 1's in the matrix, so it matches up. Notice that you start on the left when you read the graph, meaning that the rows are the origins of edges and the columns are the destinations.

For example, you can see that if you start at the 'B' row, and read across to the 'D' column, there is a 1 there as there is an edge from B to D. However, if you start at the 'D' row and go across to the 'B' column, there is a 0, as there is no edge from D to B (see image below).

More on representation

Adjacency lists and matrices are known as tabular representations. This means that you can use different ways to code them. You might use an array of linked lists to store an adjacency list, or you might use an array of objects (where each object has room to store the names of , say 5 adjacent objects).

The great (arguably) thing about using a matrix for a representation is that you can now do all sorts of fun matrix maths, like matrix multiplication (remember that?).

Another thing to remember is that you might not be able to use the representations in their current format to store all kinds of graphs. For example, if you're trying to represent a multigraph in a matrix, how do we enter it when there are 2 edges between the same 2 nodes? You would probably just enter a '2' instead of '1', but it means you've had to change the way you represent your graph. If a graph is edge weighted, you're going to need some sort of other field to store the weights of each edge.

Another note: Undirected graphs have symmetrical matrices.

The rest of these notes is about traversals, a different topic, so that's going to come in a different post.