Graph Representations (Adjacency List vs Adjacency Matrix)

Before applying graph algorithms, we need a way to store graphs in memory. The choice of representation directly affects performance, memory usage, and algorithm complexity. The two most common graph representations are the adjacency list and the adjacency matrix.

Each representation has strengths and trade-offs depending on the graph’s size and density.

Adjacency List

An adjacency list represents a graph as a collection of lists. Each vertex stores a list of vertices it is directly connected to.

Example

Graph:

A --- B
|     |
C --- D

Adjacency list:

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

Characteristics

• Stores only existing edges
• Memory efficient for sparse graphs
• Iterating over neighbors is fast
• Edge lookup is slower

Memory Complexity

Where:

• V = number of vertices
• E = number of edges

Adjacency Matrix

An adjacency matrix represents a graph using a 2D array. Each cell indicates whether an edge exists between two vertices.

Example

Vertices: A, B, C, D

    A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]

• 1 → edge exists
• 0 → no edge

Characteristics

• Constant-time edge lookup
• Simple to implement
• Memory inefficient for sparse graphs
• Iterating neighbors is slower

Memory Complexity

Directed and Weighted Graphs

Directed Graph (Adjacency List)

A → B
B → C

A → [B]
B → [C]
C → []

Weighted Graph (Adjacency Matrix)

    A  B  C
A [ 0  5  0 ]
B [ 0  0  3 ]
C [ 2  0  0 ]

Cell value represents the weight of the edge.

Rust Representation Examples

Adjacency List (Rust)

use std::collections::HashMap;

type Graph = HashMap<i32, Vec<i32>>;

fn add_edge(graph: &mut Graph, u: i32, v: i32) {
    graph.entry(u).or_default().push(v);
    graph.entry(v).or_default().push(u);
}

Adjacency Matrix (Rust)

struct Graph {
    matrix: Vec<Vec<bool>>,
}

impl Graph {
    fn new(vertices: usize) -> Self {
        Graph {
            matrix: vec![vec![false; vertices]; vertices],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.matrix[u][v] = true;
        self.matrix[v][u] = true;
    }
}

Comparison Summary

Which One Should You Use?

Choose adjacency list when:

• Graph is large and sparse
• You need fast neighbor traversal
• Memory efficiency matters

Choose adjacency matrix when:

• Graph is dense
• You need constant-time edge checks
• Graph size is small and fixed