218. When would you choose an adjacency matrix over an adjacency list?
EasyGraph algorithms
Technical
Show model answer
An adjacency matrix uses O(V²) space, answers is there an edge u-v in O(1), and enumerating neighbours of a vertex costs O(V). An adjacency list uses O(V + E) space, enumerates neighbours in O(degree), but edge lookup is O(degree) (or O(1) expected with hash sets).
Use a matrix for dense graphs (E close to V²), small V, frequent edge queries, or algorithms that are naturally matrix based such as Floyd-Warshall or transitive closure via bit sets. Use lists for sparse graphs, which is most real-world graphs, and for BFS, DFS and Dijkstra, where traversal is O(V + E) instead of O(V²).