Adjacency Matrix

Implementation

• Make a square matrix where row nth and nth column represent the nth vertex
  • Have a map between the number and the vertex
• Store the weight in for row → column, with 0 meaning no connection
• Means you need to know the number of vertices ahead of time
• Space: $O(V^2)$
  • Has a whole lot of wasted space with zeros for sparse graphs

Operations

• Connectedness
  • Check that G[A][B] is not 0
  • $O(1)$ time
• Adjacency
  • Check for all non zero values in a row of the matrix
    • for all elements in G[A]
  • $O(V)$ time