Comparison of a graph representation of an object with an adjacency list and matrix representations

Question

I am currently following Steve Yegge's advice on preparing for an interview on technical programming: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

In the "Counts" section, he states:

There are three main ways to represent a graph in memory (objects and pointers, a matrix and adjacency list), and you should familiarize yourself with each view and its pros and cons.

The pros and cons of matrix list and adjacency list representations are described in CLRS, but I could not find a resource that compares them with an object representation.

Just thinking about it, I can draw a conclusion about it myself, but I would like to make sure that I did not miss something important. If someone can describe this comprehensively or point me to a resource that does this, I would really appreciate it.

Answer 1

objects and pointers

These are just basic data structures like hammar said in another answer, in Java you could represent this with classes like edges and vertices. For example, an edge connects two vertices and can be directional or non-directional and can contain weight. A vertex can have an identifier, name, etc. Most of them have additional properties. Thus, you can build your schedule with them, for example

 Vertex a = new Vertex(1); Vertex b = new Vertex(2); Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30 

This approach is usually used for object-oriented implementations, since it is more readable and convenient for object-oriented users;).

matrix

A matrix is ​​just a simple two-dimensional array. Assuming you have a vertex identifier that can be represented as an int array as follows:

 int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1 

This is commonly used for tight graphs where index access is required. You can imagine a structure un / directional and balanced with it.

adjacency list

This is just a simple data set, I usually implement this with HashMap<Vertex, List<Vertex>> . A similar use could be the HashMultimap in Guava.

This approach is cool because you have a search for vertices O (1) (amortized) and it returns me a list of all adjacent vertices at this particular required vertex.

 ArrayList<Vertex> list = new ArrayList<>(); list.add(new Vertex(2)); list.add(new Vertex(3)); map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3 

This is used to present sparse schedules; if you are applying to Google, you should be aware that the website is sparse. You can handle them in a more scalable way using BigTable .

Oh and BTW, here is a very good summary of this post with fantastic pictures;)

Answer 2

Objects and pointers basically coincide with the adjacency list, at least to compare algorithms that use these representations.

Comparison

 struct Node { Node *neighbours[]; }; 

from

 struct Node { Node *left; Node *right; }; 

You can easily make a list of neighbors "on the fly" in the latter case, if it is easier to work with it than with the indicated pointers.

Answer 3

The advantage of representing an object (a list of incidents ) is that two adjacent vertices have the same edge instance. This makes it easy to manipulate data with non-oriented edges (length, cost, flow or direction). However, it uses extra memory for pointers.