Graph Implementation

What actually happens

Representation explorer

The graph below is identical in both views. Toggle directed/undirected to see why a symmetric matrix and two adjacency entries are implementation consequences, not extra logical edges.

Choose by operations, not habit

A hash-backed neighbor map changes the edge-query bound, but adds hashing, object, and resizing overhead. State whether your complexity assumes a list, set, matrix, or compressed layout.

Weighted edges & lookup nuance

Build safely from an edge list

Allocate all n buckets first so isolated vertices survive. Validate endpoints at the boundary, and add the reverse entry only when the input contract is undirected.

def build_graph(n, edges, directed=False):
    adj = [[] for _ in range(n)]  # keeps isolated vertices
    for u, v, weight in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint out of range")
        adj[u].append((v, weight))
        if not directed:
            adj[v].append((u, weight))
    return adj

import java.util.*;

final class GraphBuilder {
    record Edge(int to, long weight) {}

    static List<List<Edge>> buildGraph(
            int n, long[][] edges, boolean directed) {
        List<List<Edge>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        for (long[] edge : edges) {
            int u = Math.toIntExact(edge[0]);
            int v = Math.toIntExact(edge[1]);
            long weight = edge[2];
            if (u < 0 || u >= n || v < 0 || v >= n) {
                throw new IllegalArgumentException("edge endpoint out of range");
            }
            adj.get(u).add(new Edge(v, weight));
            if (!directed) adj.get(v).add(new Edge(u, weight));
        }
        return adj;
    }
}

Implementation (adjacency list)

We usually prefer the Adjacency List because most real-world graphs are sparse (not everything is connected to everything). Here's how to implement a Graph class in Python and Java using a dictionary/map.

class Graph:
    def __init__(self):
        # Dictionary to store the graph: {vertex: [neighbors]}
        self.adj_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    def add_edge(self, v1, v2):
        # Add v1 and v2 if they don't exist
        if v1 not in self.adj_list:
            self.add_vertex(v1)
        if v2 not in self.adj_list:
            self.add_vertex(v2)
        
        # Add connection (Undirected Graph)
        self.adj_list[v1].append(v2)
        self.adj_list[v2].append(v1)

    def print_graph(self):
        for vertex in self.adj_list:
            print(f"{vertex} -> {self.adj_list[vertex]}")

# Usage
my_graph = Graph()
my_graph.add_edge('A', 'B')
my_graph.add_edge('B', 'C')
my_graph.add_edge('C', 'A')

my_graph.print_graph()

# Output:
# A -> ['B', 'C']
# B -> ['A', 'C']
# C -> ['B', 'A']

import java.util.*;

class Graph {
    // Map to store graph: Vertex -> List of Neighbors
    private Map<String, List<String>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addVertex(String vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);

        // Add connection (Undirected Graph)
        adjList.get(v1).add(v2);
        adjList.get(v2).add(v1);
    }

    public void printGraph() {
        for (String vertex : adjList.keySet()) {
            System.out.println(vertex + " -> " + adjList.get(vertex));
        }
    }

    public static void main(String[] args) {
        Graph myGraph = new Graph();
        myGraph.addEdge("A", "B");
        myGraph.addEdge("B", "C");
        myGraph.addEdge("C", "A");

        myGraph.printGraph();
        
        // Output:
        // A -> [B, C]
        // B -> [A, C]
        // C -> [B, A]
    }
}

CSR: why static graphs can be faster

Implementation review checklist

• ✓ Are vertex IDs dense, sparse, or strings, and is remapping required?
• ✓ Are self-loops and parallel edges legal, ignored, or rejected?
• ✓ Can weights exceed int, and what represents “no edge” without colliding with a real weight?
• ✓ Does E count logical undirected edges once even though storage contains two entries?
• ✓ Do empty buckets preserve isolated vertices and disconnected components?
• ✓ Is the graph immutable during algorithms, or do readers need locking/versioned snapshots?

Exercises

1. Build from edges [(0,1),(1,2)] with n = 5. How many empty adjacency buckets must exist, and what goes wrong if you only create keys that appear in E?
2. An undirected add_edge updates only adj[u]. Which algorithms silently misbehave, and how would a degree-sum check catch it?
3. V = 5000, E ≈ V²/2. Would you still prefer lists for BFS? Estimate neighbor-scan work for list vs matrix.

Primary sources

• Cormen et al., Introduction to Algorithms (CLRS): adjacency-list and adjacency-matrix representations.
• Sedgewick & Wayne: Graph ADT implementations in practice.
• Scientific computing notes on CSR/CSC sparse formats (e.g. SciPy sparse documentation).