Course contentsShow
← Computer Science
Lesson 678 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Directed vs Undirected Graph Storage

Modify representation strategies to handle directed edges versus symmetric undirected edges.

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, then matrix[j][i] = 1 too. You technically only need to store half, but most implementations keep both for fast lookups.
  • Directed: No symmetry required. matrix[i][j] = 1 means an edge from vertex i to j, but matrix[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.