Directed vs Undirected Graph Storage
What you'll learn: How to adjust your graph representation to efficiently store directed edges versus undirected edges.
The Core Difference
When storing graphs, you must account for whether edges have direction. In an undirected graph, an edge between vertices A and B means both A→B and B→A exist—the relationship is symmetric. In a directed graph, an edge from A to B does not imply B to A; each direction must be stored explicitly only if it exists.
Storage Strategies by Representation
Adjacency Matrix
- Undirected: The matrix is symmetric across the diagonal. If
matrix[i][j] = 1, thenmatrix[j][i] = 1too. You technically only need to store half, but most implementations keep both for fast lookups. - Directed: No symmetry required.
matrix[i][j] = 1means an edge from vertex i to j, butmatrix[j][i]might be 0.
Adjacency List
- Undirected: When you add an edge between A and B, you must add B to A's list and A to B's list. Every edge requires two list entries.
- Directed: Add an entry only in the direction the edge points. An edge from A to B means adding B to A's adjacency list, period.
Edge List
- Undirected: Store each edge once as a pair
(A, B). Your algorithms must remember this means both directions. - Directed: Store edges as ordered pairs
(source, destination)where order matters.
Memory Impact
Undirected graphs in adjacency lists use roughly twice the memory for edge storage compared to directed graphs with the same number of edges, since each edge appears in two adjacency lists.
Key Takeaway: Undirected graphs require symmetric storage—edges must be accessible from both endpoints—while directed graphs store only the specified direction, making the choice of representation affect both memory usage and implementation logic.