There are two common implementations for graphs

- An
*adjacency matrix*represents a graph G of N nodes and E edges using an NxN boolean matrix A, where A[i][j] is true if (i,j) is an edge in G.

- An
*adjacency list*represents a graph G of N nodes and E edges as an array A of size N, where A[i] is a pointer to a list of vertices that are successors to vertex i.

If we are implementing an undirected graph

- the adjacency matrix is
*symmetric*, which means A[i,j] = A[j,i] - each edge (u,v) appears on the adjacency list for both node u and v

Consider a graph G with N nodes and E edges (0 <= E <= N^2)

- Adjacency matrix
- Is (u,v) an edge? -- O(1)
- Successors (u) -- O(N)
- Predecessor (u) -- O(N)
- Space -- O(N^2) (bits) to store the matrix
- Best for dense graphs (E ~= N^2)

- Is (u,v) an edge? -- O(1)
- Adjacency lists
- Is (u,v) an edge? -- O(E/N) on average
- Successors (u) -- O(E/N)
- Predecessor (u) -- O(N+E)
- Space -- O(N + E)
- Best for sparse graphs (E << N^2)

- Is (u,v) an edge? -- O(E/N) on average