Graph Representations — adjacency list, matrix, edge list
Graph Representations
Before you can run BFS, DFS, Dijkstra, or anything else, you have to decide how the graph lives in memory. Three options trade space against query speed.
Edge list
Just a list of (u, v) tuples. Cheap to build from input, but neighbour lookup requires scanning the whole list. Use for algorithms that iterate edges directly (Kruskal's MST).
Adjacency list
A dict-of-lists (defaultdict(list) is idiomatic). Space O(V + E). Iterating a node's neighbours is O(deg(u)). Default choice for competitive programming and real systems. Social graphs, web crawls, most road networks are sparse — list wins.
Adjacency matrix
V-by-V grid. mat[u][v] answers 'is there an edge?' in O(1). Cost is O(V²) memory. Use when dense (E approaches V²), when you need constant-time edge queries, or for algorithms working directly on the matrix (Floyd-Warshall).
Directed vs undirected
Undirected edges get added both ways in a list or matrix — miss the second write and half your BFS silently fails.
Common bugs to avoid
- Forgetting the mirror on undirected graphs.
- Using a matrix for a million-node graph. A 10⁶ × 10⁶ boolean matrix is 125 GB.
- Iterating a matrix when you want neighbours turns O(V + E) into O(V²).
Try it
- Convert the sample
edgesinto a directed adjacency list where each edge only goes from smaller to larger endpoint. - Write
degree_distribution(adj)returning aCounterof degree counts. First thing you'd compute on a real-world graph.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Build an adjacency-list dict
graphfor an undirected graph with edges (1,2), (1,3), (2,4). Every node should map to a list of its neighbors. Printgraph[1]sorted. - Exercise 2
Write
add_edge(graph, a, b, directed=False)that appends the edge to the adjacency-list dict, creating nodes on the fly. Whendirected=False(default) it adds both directions. Return the updated dict. - Exercise 3
Write
degree(graph, node)returning how many neighborsnodehas in the adjacency-list dict (0 if the node is missing). Print the degrees of 'A' and 'Z' for the sample graph.