Graph Representations

Overview

Graph representations define how graph topology is stored in memory. A graph consists of vertices (nodes) and edges (connections between vertices). The choice of representation affects memory consumption, operation speed, and implementation complexity for graph algorithms.

Three primary representations dominate software development: adjacency matrices store connections in a two-dimensional array, adjacency lists maintain a collection of neighbors for each vertex, and edge lists enumerate all connections as pairs. Each representation optimizes different operations at the cost of others.

# Adjacency list representation
graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D'],
  'C' => ['A', 'D'],
  'D' => ['B', 'C']
}

# Adjacency matrix representation
matrix = [
  [0, 1, 1, 0],  # A connects to B, C
  [1, 0, 0, 1],  # B connects to A, D
  [1, 0, 0, 1],  # C connects to A, D
  [0, 1, 1, 0]   # D connects to B, C
]

Graph representations serve as the foundation for implementing shortest path algorithms, network flow, social network analysis, dependency resolution, and route planning. The representation choice impacts both the asymptotic complexity and constant factors in algorithm performance.

Directed graphs require asymmetric edge storage where an edge from vertex u to vertex v does not imply an edge from v to u. Undirected graphs store bidirectional connections. Weighted graphs associate numerical values with edges, requiring additional storage beyond simple connectivity information.

Key Principles

Graph representations encode two fundamental pieces of information: vertex existence and edge connectivity. The vertex set V contains all nodes in the graph. The edge set E contains all connections, where each edge links two vertices. A representation must support querying both vertex properties and edge relationships.

Adjacency Matrix uses a |V| × |V| two-dimensional array where entry (i, j) indicates whether an edge exists from vertex i to vertex j. For unweighted graphs, entries contain boolean values or 0/1 integers. For weighted graphs, entries store edge weights with a sentinel value (often infinity or nil) representing absent edges.

# Weighted adjacency matrix
INFINITY = Float::INFINITY
matrix = [
  [0,      5,      INFINITY, 10],
  [INFINITY, 0,    3,        INFINITY],
  [INFINITY, INFINITY, 0,    1],
  [INFINITY, INFINITY, INFINITY, 0]
]
# matrix[0][1] = 5 means edge from vertex 0 to vertex 1 with weight 5

The matrix representation provides O(1) edge existence queries by direct array indexing. Adding or removing edges requires O(1) time. The space complexity remains Θ(|V|²) regardless of edge density, making matrices inefficient for sparse graphs but acceptable for dense graphs where |E| approaches |V|².

Adjacency List maintains a collection of neighbors for each vertex. Common implementations use hash tables mapping vertices to arrays, sets, or linked lists of adjacent vertices. This representation scales storage with the number of edges rather than vertices.

# Adjacency list with arrays
adj_list = {
  0 => [1, 3],
  1 => [2],
  2 => [3],
  3 => []
}

# With weights as tuples
weighted_adj_list = {
  0 => [[1, 5], [3, 10]],
  1 => [[2, 3]],
  2 => [[3, 1]],
  3 => []
}

Adjacency lists consume Θ(|V| + |E|) space, optimal for sparse graphs. Edge existence queries require O(degree(v)) time where degree(v) represents the number of edges from vertex v. Iterating over all neighbors of a vertex takes O(degree(v)) time, proportional to actual neighbor count rather than total vertex count.

Edge List stores edges as a flat collection of vertex pairs. This representation works well for algorithms that process edges sequentially rather than vertex-by-vertex.

edges = [
  [0, 1],
  [0, 3],
  [1, 2],
  [2, 3]
]

# Weighted edges
weighted_edges = [
  [0, 1, 5],
  [0, 3, 10],
  [1, 2, 3],
  [2, 3, 1]
]

Edge lists use Θ(|E|) space, minimal among all representations. Edge existence queries require O(|E|) time as they necessitate scanning the entire list. This representation suits algorithms like Kruskal's minimum spanning tree that sort or iterate through all edges.

Incidence Matrix uses a |V| × |E| array where rows represent vertices and columns represent edges. Entry (v, e) indicates whether vertex v is incident to edge e. For directed graphs, values distinguish between source and target vertices.

The incidence matrix representation appears less frequently in practice due to its space complexity and limited performance benefits. It finds applications in theoretical graph analysis and specific mathematical computations involving graph Laplacians.

Implementation Approaches

Graph representation selection depends on graph density, expected operations, and memory constraints. Sparse graphs with |E| << |V|² benefit from adjacency lists. Dense graphs with |E| ≈ |V|² show less difference between representations. Directed and undirected graphs share the same representation strategies with different edge storage semantics.

Adjacency Matrix Strategy suits dense graphs or scenarios requiring frequent edge existence queries. The matrix provides constant-time access to any edge but wastes space on absent edges in sparse graphs. Matrix implementations align well with linear algebra operations on graphs.

The matrix approach stores vertices implicitly through array indices. Adding a vertex requires allocating a new matrix with dimension (|V| + 1) × (|V| + 1) and copying existing data, an O(|V|²) operation. This makes adjacency matrices inflexible for dynamic graphs with frequent vertex additions.

For undirected graphs, the adjacency matrix becomes symmetric with entry (i, j) equal to entry (j, i). Storing only the upper or lower triangle reduces space consumption by half but complicates access patterns.

Adjacency List Strategy excels for sparse graphs and algorithms that iterate through neighbors. The list representation stores only existing edges, minimizing memory usage. Hash table implementations provide O(1) average-case vertex lookup.

# Using Set for constant-time neighbor checks
require 'set'

adj_list = Hash.new { |h, k| h[k] = Set.new }
adj_list[0].add(1)
adj_list[0].add(3)
adj_list[1].add(2)

# Check edge existence
adj_list[0].include?(1)  # => true

The adjacency list grows dynamically as edges are added. Vertex addition requires O(1) time to insert a new empty neighbor collection. Edge removal requires searching the neighbor collection, taking O(degree(v)) time for array-based lists or O(1) average-case time for set-based lists.

Adjacency lists handle both directed and undirected graphs naturally. For undirected graphs, each edge appears in two adjacency lists. For directed graphs, each edge appears only in the source vertex's list. Storing reverse edges in a separate structure accelerates algorithms that traverse graphs backward.

Edge List Strategy provides a minimal representation suitable for specific algorithms. Edge lists work well when processing all edges uniformly without focusing on particular vertices. The representation supports efficient sorting by weight or other edge attributes.

Edge list implementations use arrays, linked lists, or priority queues depending on access patterns. Adding edges takes O(1) time by appending to the list. Removing specific edges requires O(|E|) time to locate and delete entries.

Hybrid Strategies combine multiple representations to optimize different operations. Storing both an adjacency list and an edge list provides fast neighbor iteration and efficient edge enumeration. The dual representation doubles space consumption but eliminates conversion overhead when both access patterns occur.

# Hybrid representation
class Graph
  attr_reader :adj_list, :edges
  
  def initialize
    @adj_list = Hash.new { |h, k| h[k] = [] }
    @edges = []
  end
  
  def add_edge(u, v, weight = 1)
    @adj_list[u] << [v, weight]
    @edges << [u, v, weight]
  end
end

Ruby Implementation

Ruby provides flexible data structures for implementing graph representations through hashes, arrays, and sets. Hash-based adjacency lists offer the most idiomatic approach, combining dynamic growth with fast lookups.

Basic Adjacency List

class Graph
  def initialize(directed: false)
    @adj_list = Hash.new { |h, k| h[k] = [] }
    @directed = directed
  end
  
  def add_vertex(vertex)
    @adj_list[vertex] ||= []
  end
  
  def add_edge(from, to, weight: 1)
    @adj_list[from] << { vertex: to, weight: weight }
    @adj_list[to] << { vertex: from, weight: weight } unless @directed
  end
  
  def neighbors(vertex)
    @adj_list[vertex].map { |edge| edge[:vertex] }
  end
  
  def edge_weight(from, to)
    edge = @adj_list[from].find { |e| e[:vertex] == to }
    edge ? edge[:weight] : nil
  end
  
  def vertices
    @adj_list.keys
  end
  
  def edges
    result = []
    @adj_list.each do |from, neighbors|
      neighbors.each do |edge|
        result << [from, edge[:vertex], edge[:weight]]
      end
    end
    @directed ? result : result.uniq { |u, v, w| [u, v].sort }
  end
end

graph = Graph.new(directed: true)
graph.add_edge('A', 'B', weight: 5)
graph.add_edge('A', 'C', weight: 3)
graph.add_edge('B', 'C', weight: 2)

graph.neighbors('A')  # => ['B', 'C']
graph.edge_weight('A', 'B')  # => 5

The implementation uses hashes with default block initialization to create empty arrays for new vertices automatically. Edge data structures use hashes to store target vertices and weights together, providing clear attribute access.

Adjacency Matrix Implementation

class MatrixGraph
  def initialize(size)
    @matrix = Array.new(size) { Array.new(size, nil) }
    @vertex_map = {}
    @next_index = 0
  end
  
  def add_vertex(vertex)
    return if @vertex_map.key?(vertex)
    
    if @next_index >= @matrix.size
      expand_matrix
    end
    
    @vertex_map[vertex] = @next_index
    @next_index += 1
  end
  
  def add_edge(from, to, weight: 1)
    add_vertex(from)
    add_vertex(to)
    
    from_idx = @vertex_map[from]
    to_idx = @vertex_map[to]
    @matrix[from_idx][to_idx] = weight
  end
  
  def edge_weight(from, to)
    from_idx = @vertex_map[from]
    to_idx = @vertex_map[to]
    return nil unless from_idx && to_idx
    
    @matrix[from_idx][to_idx]
  end
  
  def neighbors(vertex)
    idx = @vertex_map[vertex]
    return [] unless idx
    
    neighbors = []
    @matrix[idx].each_with_index do |weight, to_idx|
      neighbors << vertex_at(to_idx) if weight
    end
    neighbors
  end
  
  private
  
  def vertex_at(index)
    @vertex_map.key(index)
  end
  
  def expand_matrix
    new_size = @matrix.size * 2
    new_matrix = Array.new(new_size) { Array.new(new_size, nil) }
    
    @matrix.each_with_index do |row, i|
      row.each_with_index do |val, j|
        new_matrix[i][j] = val
      end
    end
    
    @matrix = new_matrix
  end
end

graph = MatrixGraph.new(10)
graph.add_edge('A', 'B', weight: 5)
graph.add_edge('A', 'C', weight: 3)

graph.edge_weight('A', 'B')  # => 5
graph.neighbors('A')  # => ['B', 'C']

The matrix implementation maintains a separate vertex-to-index mapping since Ruby does not enforce integer vertex labels. The expand_matrix method handles dynamic growth, though this operation remains expensive at O(|V|²).

Optimized Adjacency List with Sets

require 'set'

class FastGraph
  def initialize(directed: false)
    @adj_list = Hash.new { |h, k| h[k] = Set.new }
    @weights = {}
    @directed = directed
  end
  
  def add_edge(from, to, weight: 1)
    @adj_list[from].add(to)
    @weights[[from, to]] = weight
    
    unless @directed
      @adj_list[to].add(from)
      @weights[[to, from]] = weight
    end
  end
  
  def remove_edge(from, to)
    @adj_list[from].delete(to)
    @weights.delete([from, to])
    
    unless @directed
      @adj_list[to].delete(from)
      @weights.delete([to, from])
    end
  end
  
  def edge?(from, to)
    @adj_list[from].include?(to)
  end
  
  def edge_weight(from, to)
    @weights[[from, to]]
  end
  
  def degree(vertex)
    @adj_list[vertex].size
  end
  
  def neighbors(vertex)
    @adj_list[vertex].to_a
  end
end

graph = FastGraph.new(directed: true)
graph.add_edge('A', 'B', weight: 5)
graph.add_edge('A', 'C', weight: 3)

graph.edge?('A', 'B')  # => true
graph.degree('A')  # => 2
graph.remove_edge('A', 'B')
graph.edge?('A', 'B')  # => false

Using Set for neighbor storage reduces edge existence queries from O(degree(v)) to O(1) average case. The separate weights hash stores edge weights indexed by [from, to] tuples, decoupling connectivity from weight information.

Edge List Implementation

class EdgeListGraph
  Edge = Struct.new(:from, :to, :weight)
  
  def initialize(directed: false)
    @edges = []
    @vertices = Set.new
    @directed = directed
  end
  
  def add_vertex(vertex)
    @vertices.add(vertex)
  end
  
  def add_edge(from, to, weight: 1)
    @vertices.add(from)
    @vertices.add(to)
    @edges << Edge.new(from, to, weight)
  end
  
  def edges
    @edges
  end
  
  def vertices
    @vertices.to_a
  end
  
  def edges_from(vertex)
    @edges.select { |e| e.from == vertex }
  end
  
  def sort_by_weight!
    @edges.sort_by!(&:weight)
  end
  
  def edge_count
    @directed ? @edges.size : @edges.size / 2
  end
end

graph = EdgeListGraph.new(directed: true)
graph.add_edge('A', 'B', weight: 10)
graph.add_edge('B', 'C', weight: 5)
graph.add_edge('A', 'C', weight: 15)

graph.sort_by_weight!
graph.edges.first  # => #<struct Edge from="B", to="C", weight=5>

The edge list uses a Struct for type-safe edge representation. This implementation suits algorithms that iterate through all edges or require edges sorted by weight. Filtering edges by source vertex takes O(|E|) time but remains acceptable when this operation occurs infrequently.

Performance Considerations

Space and time complexity vary significantly across graph representations. The choice impacts algorithm efficiency, especially for graphs with millions of vertices or edges.

Space Complexity Analysis

Adjacency matrices consume Θ(|V|²) space regardless of edge count. A graph with 10,000 vertices requires 100 million entries, typically 400MB for 32-bit integers. This becomes prohibitive for sparse graphs where most entries remain empty.

Adjacency lists require Θ(|V| + |E|) space. Each vertex stores a collection reference, and each edge appears once (directed) or twice (undirected). For a sparse graph with 10,000 vertices and 50,000 edges, an adjacency list consumes approximately 10,000 + 100,000 = 110,000 entries, about 440KB with 32-bit integers and pointers.

Edge lists use Θ(|E|) space, storing only edge information. This provides the minimal space requirement but lacks vertex metadata storage. For 50,000 edges with weights, the representation needs roughly 600KB (12 bytes per edge).

Operation Time Complexity

The degree term in adjacency list operations represents the number of edges from a vertex. For sparse graphs, degree << |V|, making adjacency list operations much faster than matrix operations that must scan entire rows.

Practical Performance Characteristics

Ruby's hash implementation provides O(1) average-case lookup through open addressing. Set operations inherit this performance. For adjacency lists using hashes and sets, edge existence queries complete in microseconds even for vertices with thousands of neighbors.

require 'benchmark'
require 'set'

# Compare edge existence query performance
def benchmark_edge_query(vertex_count, edge_count)
  # Build adjacency list
  adj_list = Hash.new { |h, k| h[k] = Set.new }
  edge_count.times do
    u = rand(vertex_count)
    v = rand(vertex_count)
    adj_list[u].add(v)
  end
  
  # Build adjacency matrix
  matrix = Array.new(vertex_count) { Array.new(vertex_count, false) }
  adj_list.each do |u, neighbors|
    neighbors.each { |v| matrix[u][v] = true }
  end
  
  # Benchmark queries
  queries = 10000
  Benchmark.bm(15) do |x|
    x.report("adj_list:") do
      queries.times do
        u = rand(vertex_count)
        v = rand(vertex_count)
        adj_list[u].include?(v)
      end
    end
    
    x.report("matrix:") do
      queries.times do
        u = rand(vertex_count)
        v = rand(vertex_count)
        matrix[u][v]
      end
    end
  end
end

benchmark_edge_query(1000, 5000)
# adj_list:        0.003s
# matrix:          0.002s

For edge existence queries, matrices slightly outperform adjacency lists due to direct array indexing versus hash lookup. The difference remains small in absolute terms but becomes relevant in tight loops processing millions of queries.

Neighbor iteration shows dramatic differences. Adjacency lists iterate only over actual neighbors in O(degree) time. Matrices must scan entire rows, taking O(|V|) time regardless of actual neighbor count.

# Neighbor iteration comparison
def benchmark_neighbor_iteration(vertex_count, avg_degree)
  edge_count = vertex_count * avg_degree
  
  adj_list = Hash.new { |h, k| h[k] = [] }
  edge_count.times do
    u = rand(vertex_count)
    v = rand(vertex_count)
    adj_list[u] << v
  end
  
  matrix = Array.new(vertex_count) { Array.new(vertex_count, false) }
  adj_list.each do |u, neighbors|
    neighbors.each { |v| matrix[u][v] = true }
  end
  
  iterations = 1000
  Benchmark.bm(15) do |x|
    x.report("adj_list:") do
      iterations.times do
        vertex = rand(vertex_count)
        adj_list[vertex].each { |n| n }
      end
    end
    
    x.report("matrix:") do
      iterations.times do
        vertex = rand(vertex_count)
        matrix[vertex].each_with_index { |exists, n| n if exists }
      end
    end
  end
end

benchmark_neighbor_iteration(1000, 10)
# avg_degree = 10, sparse graph
# adj_list:        0.001s
# matrix:          0.156s

For sparse graphs, adjacency list neighbor iteration runs 100x faster than matrix scanning. This performance gap drives the preference for adjacency lists in graph algorithm implementations.

Cache Locality Considerations

Adjacency matrices benefit from sequential memory access patterns. Modern CPUs prefetch array elements, making matrix row scans cache-efficient. Adjacency lists scatter edge data across memory through pointer-based structures, causing more cache misses.

For dense graphs processed with full matrix traversal, the cache advantage can offset adjacency list algorithmic benefits. Graph algorithms that repeatedly scan all edges from all vertices may run faster with matrix representations despite higher asymptotic complexity.

Practical Examples

Social Network Graph

Social networks represent users as vertices and friendships as edges. The graph remains sparse since each user connects to a small fraction of total users.

class SocialNetwork
  def initialize
    @friendships = Hash.new { |h, k| h[k] = Set.new }
    @users = {}
  end
  
  def add_user(id, name)
    @users[id] = name
    @friendships[id] ||= Set.new
  end
  
  def add_friendship(user1, user2)
    @friendships[user1].add(user2)
    @friendships[user2].add(user1)
  end
  
  def friends(user_id)
    @friendships[user_id].map { |id| @users[id] }
  end
  
  def mutual_friends(user1, user2)
    common = @friendships[user1] & @friendships[user2]
    common.map { |id| @users[id] }
  end
  
  def friend_of_friend_count(user_id)
    fof = Set.new
    @friendships[user_id].each do |friend|
      @friendships[friend].each do |fof_candidate|
        fof.add(fof_candidate) unless fof_candidate == user_id
      end
    end
    fof.size - @friendships[user_id].size
  end
end

network = SocialNetwork.new
network.add_user(1, "Alice")
network.add_user(2, "Bob")
network.add_user(3, "Carol")
network.add_user(4, "Dave")

network.add_friendship(1, 2)
network.add_friendship(1, 3)
network.add_friendship(2, 3)
network.add_friendship(3, 4)

network.friends(1)  # => ["Bob", "Carol"]
network.mutual_friends(1, 2)  # => ["Carol"]
network.friend_of_friend_count(1)  # => 1 (Dave)

The social network uses an adjacency list with Set for efficient friendship queries. Set intersection provides fast mutual friend computation. The friend-of-friend calculation demonstrates graph traversal patterns common in social network analysis.

Dependency Graph

Package managers and build systems represent dependencies as directed acyclic graphs (DAGs). Each package depends on other packages, forming edges from dependent to dependency.

class DependencyGraph
  def initialize
    @dependencies = Hash.new { |h, k| h[k] = Set.new }
    @reverse_deps = Hash.new { |h, k| h[k] = Set.new }
  end
  
  def add_dependency(package, depends_on)
    @dependencies[package].add(depends_on)
    @reverse_deps[depends_on].add(package)
  end
  
  def direct_dependencies(package)
    @dependencies[package].to_a
  end
  
  def dependents(package)
    @reverse_deps[package].to_a
  end
  
  def topological_sort
    in_degree = Hash.new(0)
    @dependencies.each do |pkg, deps|
      in_degree[pkg] ||= 0
      deps.each { |dep| in_degree[dep] += 1 }
    end
    
    queue = in_degree.select { |_, deg| deg == 0 }.map(&:first)
    result = []
    
    while !queue.empty?
      pkg = queue.shift
      result << pkg
      
      @reverse_deps[pkg].each do |dependent|
        in_degree[dependent] -= 1
        queue << dependent if in_degree[dependent] == 0
      end
    end
    
    result
  end
end

deps = DependencyGraph.new
deps.add_dependency('app', 'database')
deps.add_dependency('app', 'auth')
deps.add_dependency('database', 'config')
deps.add_dependency('auth', 'config')

deps.topological_sort  # => ["config", "database", "auth", "app"]

This implementation maintains both forward and reverse edges for efficient queries in both directions. The topological sort determines build order, ensuring dependencies are processed before dependents.

Weighted Road Network

Transportation networks model intersections as vertices and roads as weighted edges where weights represent distance or travel time.

class RoadNetwork
  def initialize
    @roads = Hash.new { |h, k| h[k] = {} }
    @locations = {}
  end
  
  def add_location(id, name, lat, lon)
    @locations[id] = { name: name, lat: lat, lon: lon }
  end
  
  def add_road(from, to, distance, bidirectional: true)
    @roads[from][to] = distance
    @roads[to][from] = distance if bidirectional
  end
  
  def shortest_path_dijkstra(start, goal)
    distances = Hash.new(Float::INFINITY)
    distances[start] = 0
    previous = {}
    unvisited = @roads.keys.to_set
    
    while !unvisited.empty?
      current = unvisited.min_by { |v| distances[v] }
      break if current == goal || distances[current] == Float::INFINITY
      
      unvisited.delete(current)
      
      @roads[current].each do |neighbor, distance|
        next unless unvisited.include?(neighbor)
        
        alt_distance = distances[current] + distance
        if alt_distance < distances[neighbor]
          distances[neighbor] = alt_distance
          previous[neighbor] = current
        end
      end
    end
    
    # Reconstruct path
    path = []
    current = goal
    while current
      path.unshift(current)
      current = previous[current]
    end
    
    { path: path, distance: distances[goal] }
  end
end

network = RoadNetwork.new
network.add_location(1, "Downtown", 40.7128, -74.0060)
network.add_location(2, "Midtown", 40.7489, -73.9680)
network.add_location(3, "Uptown", 40.7829, -73.9654)
network.add_location(4, "Airport", 40.6413, -73.7781)

network.add_road(1, 2, 5.2)
network.add_road(2, 3, 3.8)
network.add_road(1, 4, 15.6)
network.add_road(2, 4, 12.3)

result = network.shortest_path_dijkstra(1, 4)
# => { path: [1, 2, 4], distance: 17.5 }

The road network stores weights in nested hashes, providing O(1) average-case edge weight lookup. Dijkstra's algorithm demonstrates how adjacency list representations facilitate graph traversal algorithms that process neighbors repeatedly.

Design Considerations

Graph representation selection requires analyzing graph characteristics and expected operations. No single representation dominates across all scenarios.

Density Analysis

Graph density ρ = |E| / (|V| × (|V| - 1)) measures edge count relative to maximum possible edges. Sparse graphs have ρ << 1, dense graphs have ρ ≈ 1.

For sparse graphs (ρ < 0.1), adjacency lists provide substantial space savings. A graph with 1,000 vertices and 5,000 edges achieves density ρ = 5,000 / (1,000 × 999) ≈ 0.005. An adjacency list uses approximately 1,000 + 10,000 = 11,000 entries (undirected graph stores edges twice). A matrix requires 1,000,000 entries, wasting 99% of storage on absent edges.

For dense graphs (ρ > 0.5), matrices become competitive. A graph with 1,000 vertices and 400,000 edges requires 800,000 adjacency list entries versus 1,000,000 matrix entries, a smaller difference.

Operation Frequency Profile

Algorithms dominated by edge existence queries favor matrices. Graph coloring algorithms repeatedly check whether vertices share edges, making O(1) matrix queries attractive despite O(|V|²) space cost.

Algorithms dominated by neighbor iteration favor adjacency lists. Breadth-first search processes each vertex's neighbors sequentially, wasting time scanning matrix rows filled with absent edges.

Algorithms processing edges uniformly favor edge lists. Minimum spanning tree algorithms using Kruskal's method sort all edges by weight, an operation natural for edge lists but requiring extraction from adjacency matrices or lists.

Dynamic Graph Requirements

Graphs with frequent vertex additions favor adjacency lists. Adding a vertex to an adjacency list takes O(1) time. Adding a vertex to an adjacency matrix requires allocating a larger matrix and copying existing data, an O(|V|²) operation that becomes prohibitive for large graphs.

Graphs with frequent edge additions and deletions favor structures supporting efficient modification. Adjacency lists using sets allow O(1) average-case edge addition and deletion. Edge lists support O(1) addition but O(|E|) deletion.

Memory Access Patterns

Algorithms with sequential access patterns benefit from matrix cache locality. Iterating through matrix rows accesses contiguous memory, enabling CPU prefetching. Traversing adjacency lists follows pointers scattered across memory, causing cache misses.

Algorithms with random access patterns benefit from adjacency list space efficiency. Small working sets fit in cache despite pointer indirection. Large matrices thrash cache even with sequential access.

Trade-off Decision Framework

Select adjacency lists when:

• Graph remains sparse (ρ < 0.1)
• Neighbor iteration dominates operations
• Dynamic vertex additions occur frequently
• Memory constraints limit available space

Select adjacency matrices when:

• Graph approaches density (ρ > 0.5)
• Edge existence queries dominate operations
• Graph size stays fixed and small (|V| < 1000)
• Cache locality benefits offset space overhead

Select edge lists when:

• Algorithm processes edges uniformly
• Edge sorting by weight required
• Minimal space consumption critical
• Neighbor iteration unnecessary

Select hybrid representations when:

• Multiple access patterns occur frequently
• Space permits redundant storage
• Conversion overhead exceeds storage cost
• Algorithm phases require different representations

Reference

Representation Comparison

Ruby Implementation Patterns

Operation Selection Guide

Graph Types and Default Representations

Memory Usage Estimates

Memory calculations assume 32-bit integers, 64-bit pointers where applicable, and undirected edges stored bidirectionally in lists.

Common Graph Algorithms and Representation Preference

Ruby Gems for Graph Operations