Graph representations

Graph is one of the most important data structure in computer science. There are several ways to represent graphs, each with its advantages and disadvantages. Some situations, or algorithms that we want to run with graphs as input, call for one representation, and others call for a different representation. Here, we'll see three ways to represent graphs.

Edge lists: One simple way to represent a graph is just a list, or array, of |E|∣E∣ edges, which we call an edge list. Since each edge contains just two or three numbers, the total space for an edge list is Theta Θ(E). For example, here's how we represent an edge list in JavaScript for the social network graph:

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],[3,8], [4,5], [4,9], [7,8], [7,9] ]

Edge lists are simple, but if we want to find whether the graph contains a particular edge, we have to search through the edge list. If the edges appear in the edge list in no particular order, that's a linear search through |∣E∣ edges.

Adjacency matrices: For a graph with |V| vertices, an adjacency matrix is a |V| times ∣V∣×∣V∣ matrix of 0s and 1s, where the entry in row i and column j is 1 if and only if the edge (i,j)(i,j) is in the graph.

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],

  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],

  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],

  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],

  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],

  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],

  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],

  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],

  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],

  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

Advantages

• we can find out whether an edge is present in constant time

Disadvantages:

•  First, it takes Theta(V^2) space. In other words, for a sparse graph, the adjacency matrix is mostly 0s, and we use lots of space to represent only a few edges
• Second, if you want to find out which vertices are adjacent to a given vertex ii, you have to look at all ∣V∣ entries in row ii, even if only a small number of vertices are adjacent to vertex ii.

For an undirected graph, the adjacency matrix is symmetric: the row ii, column jj entry is 1 if and only if the row jj, column ii entry is 1. For a directed graph, the adjacency matrix need not be symmetric.

Adjacency lists: An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists

Vertex numbers in an adjacency list are not required to appear in any particular order, though it is often convenient to list them in increasing order, as in this example.

[ [1, 6, 8],

  [0, 4, 6, 9],

  [4, 6],

  [4, 5, 8],

  [1, 2, 3, 5, 9],

  [3, 4],

  [0, 1, 2],

  [8, 9],

  [0, 3, 7],

  [1, 4, 7] ]

We can get to each vertex's adjacency list in constant time, because we just have to index into an array. To find out whether an edge (i,j) is present in the graph, we go to i's adjacency list in constant time and then look for j in i's adjacency list. How long does that take in the worst case? The answer is Θ(d), where dd is the degree of vertex i, because that's how long i's adjacency list is.

for (var j = 0; j < graph[i].length; j++) {

    doStuff(graph[i][j]);

}