Lesson 172
Graph Representation
Matrix vs List
1:00How to store a graph in memory using an adjacency matrix or adjacency list, and how to choose between them based on density and workload.
By the end, you can
- Construct the adjacency matrix and adjacency list for a small undirected graph.
- State the space complexity of each representation and explain why they differ for sparse vs dense graphs.
- Compare the time cost of an edge check, neighbour listing, and add/remove operations for both representations.
- Explain how symmetry in the matrix and dual-storage in the list relate to undirected edges.
- Describe how directed and weighted graphs change each representation.
- Choose the appropriate representation given a graph's density and the dominant operations of the algorithm.
Up next in Algorithms & Graph Algorithms
