Three ways to store a graph in memory, advantages and disadvantages

There are three ways to store a graph in memory:

1. Nodes as objects and edges as pointers
2. A matrix containing all edge weights between numbered node x and node y
3. A list of edges between numbered nodes

I know how to write all three, but I'm not sure I've thought of all of the advantages and disadvantages of each.

What are the advantages and disadvantages of each of these ways of storing a graph in memory?

Solution 1:

One way to analyze these is in terms of memory and time complexity (which depends on how you want to access the graph).

Storing nodes as objects with pointers to one another

• The memory complexity for this approach is O(n) because you have as many objects as you have nodes. The number of pointers (to nodes) required is up to O(n^2) as each node object may contain pointers for up to n nodes.
• The time complexity for this data structure is O(n) for accessing any given node.

Storing a matrix of edge weights

• This would be a memory complexity of O(n^2) for the matrix.
• The advantage with this data structure is that the time complexity to access any given node is O(1).

Depending on what algorithm you run on the graph and how many nodes there are, you'll have to choose a suitable representation.

Solution 2:

A couple more things to consider:

1. The matrix model lends itself more easily to graphs with weighted edges, by storing the weights in the matrix. The object/pointer model would need to store edge weights in a parallel array, which requires synchronization with the pointer array.

2. The object/pointer model works better with directed graphs than undirected graphs because the pointers would need to be maintained in pairs, which can become unsynchronized.