Graph Implementations

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

Comparison of Implementations

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)

• 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)