Object and Pointer Graph representations

Question

I keep seeing everywhere that there are 3 ways to represent graphs:

1. Objects and pointers
2. Adjacency matrix
3. Adjacency lists

However, I just plain don't understand what these Object and pointer representations are - yet every recruiter, and many blogs cite Steve Yegge's blog that they are indeed a separate representation.

This widely accepted answer to a very similar question seems to suggest that the vertex structures themselves have no internal pointers to other vertices, and instead all edges are represented by edge structures which contain pointers to the adjacent vertices.

How does this representation offer any discernible analytical advantage in any scenario?

Answer 1

From the top of my head, I hope I have the facts correct.

Conceptually, graph tries to represent how a set of nodes (or vertices) are related (connected) to each other (via edges). However, in actual physical device (memory), we have a continuous array of memory cell.

So, in order to represent the graph, we can choose to use a matrix. In this case, we use the vertex index as the row and column and the entry has value 1 if the vertices are adjacent to each other, 0 otherwise.

Alternatively, you can also represent a graph by allocating an object to represent the node/vertex which points to a list of all the nodes that are adjacent to it.

The matrix representation gives the advantage when the graph is dense, meaning when most of the nodes/vertices are connected to each other. This is because in such cases, by using the entry of matrix, it saves us from having to allocate an extra pointer (which need a word size memory) for each connection.

For sparse graph, the list approach is better because you don't need to account for the 0 entries when there is no connection between the vertices.

Hope it helps.