Card 08/ 08
Recap: Graph Representations
Three properties, both directions for an undirected edge, and density deciding list or matrix.
Graph representations come down to the six ideas below, each listed with the card that covers it. One question links them: how many of the possible edges exist, because that sets the cost of every representation.
| The idea | Where |
|---|---|
| A graph is vertices and edges, described as directed or not, weighted or not and cyclic or not, with costs stated in V and E | Graphs: Vertices, Edges and Their Properties |
| An adjacency list is built from an edge list in O(V + E), appending each end of an edge to the other's list | Build an Adjacency List From an Edge List |
| An undirected edge is stored under both ends, so the list holds 2E entries; storing it once hides neighbours | Storing an Undirected Edge Only Once |
| An adjacency matrix checks an edge in O(1) and takes V² cells; it is symmetric when the graph is undirected | The Adjacency Matrix |
| Density decides: the list for a sparse graph, the matrix for a dense one, an edge list for sorting edges | Adjacency List vs Adjacency Matrix |
| No standard library has a graph type; a map of lists and a grid of numbers are built by hand | Graph Representations in Python, Java and TypeScript |
One graph, five vertices and six edges, ran through the topic, so its three representations can be set side by side: 6 pairs in the edge list, 12 entries in the adjacency list, and 25 cells in the matrix, 12 of them set. The costs that separate them are these, for V vertices and E edges.
| Operation | Adjacency list | Adjacency matrix | Edge list |
|---|---|---|---|
| Check edge u-v | O(degree of u) | O(1) | O(E) |
| List the neighbours of v | O(degree of v) | O(V) | O(E) |
| Memory | O(V + E) | O(V²) | O(E) |
Together they let you describe any graph by its properties, build its adjacency list or matrix by hand or in code, catch an undirected edge stored once, and choose the representation from the graph's density and the questions the code will ask.
← → move through sections and cards