What is Adjacency Matrix?

•      The adjacency matrix is a dense representation

–     Usually too much storage for large graphs

–     But can be very efficient for small graphs

•      Most large interesting graphs are sparse

–     For this reason the adjacency list is often a more appropriate representation

•      How much storage does the adjacency matrix require?

•      Ans: O(V²)

•      What is the minimum amount of storage needed by an adjacency matrix representation of an undirected graph with 4 vertices?

•      Ans: 6 bits

–     Undirected graph ® matrix is symmetric

–     No self-loops ® don’t need diagonal