List some ways of representing Graphs

• Edge Lists. We have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on (plus weight). 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.

[ [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] ]

• Adjacency Matrices. With an adjacency matrix, we can find out whether an edge is present in constant time, by just looking up the corresponding entry in the matrix – we can query whether edge (i, j) is in the graph by looking at graph[i][j] value. For a sparse graph, the adjacency matrix is mostly 0s, and we use lots of space to represent only a few edges. For an undirected graph, the adjacency matrix is symmetric.

[ [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] ]

• Adjacency Lists. For each vertex i, store an array of the vertices adjacent to it (or array of tuples for weighted graph). 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.

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