Graph Representation

March 31, 2026

#graph #adjacency-matrix #adjacency-list #data-structures #interviewing

Introduction

Before you can run BFS, DFS, or any other graph algorithm, you need to decide how to store the graph in memory. That choice affects the time and space complexity of every operation you perform on it.

There are two standard representations: the adjacency list and the adjacency matrix. This tutorial covers both, when to use each, and how to handle directed, undirected, and weighted graphs. You should be familiar with Graphs Introduction and Arrays before reading this.

Most real-world graphs are sparse (far fewer edges than the maximum possible), so adjacency lists are the default choice. Use an adjacency matrix when you need O(1) edge lookups or the graph is dense.

Quick reference

Consider this graph:

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

Vertices: A, B, C, D, E — Edges: A-B, A-C, B-D, C-D, D-E

As an adjacency list

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

Each vertex stores a list of its neighbors.

As an adjacency matrix

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

A 2D grid where matrix[i][j] = 1 means there’s an edge from vertex i to vertex j.

Adjacency List

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1); // remove for directed
  }

  removeEdge(v1, v2) {
    this.adjacencyList.set(v1, this.adjacencyList.get(v1).filter(v => v !== v2));
    this.adjacencyList.set(v2, this.adjacencyList.get(v2).filter(v => v !== v1));
  }

  removeVertex(vertex) {
    for (const neighbor of this.adjacencyList.get(vertex) || []) {
      this.removeEdge(vertex, neighbor);
    }
    this.adjacencyList.delete(vertex);
  }

  hasEdge(v1, v2) {
    return this.adjacencyList.get(v1)?.includes(v2) || false;
  }

  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }

  print() {
    for (const [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} → [${neighbors.join(', ')}]`);
    }
  }
}

const g = new Graph();
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');
g.print();
// A → [B, C]
// B → [A, D]
// C → [A, D]
// D → [B, C, E]
// E → [D]

console.log(g.hasEdge('A', 'B'));  // true
console.log(g.hasEdge('A', 'E'));  // false

class Graph:
    def __init__(self):
        self.adjacency_list = {}

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

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)
        self.adjacency_list[v2].append(v1)  # remove for directed

    def remove_edge(self, v1, v2):
        self.adjacency_list[v1] = [v for v in self.adjacency_list[v1] if v != v2]
        self.adjacency_list[v2] = [v for v in self.adjacency_list[v2] if v != v1]

    def remove_vertex(self, vertex):
        for neighbor in self.adjacency_list.get(vertex, []):
            self.adjacency_list[neighbor] = [
                v for v in self.adjacency_list[neighbor] if v != vertex
            ]
        del self.adjacency_list[vertex]

    def has_edge(self, v1, v2):
        return v2 in self.adjacency_list.get(v1, [])

    def get_neighbors(self, vertex):
        return self.adjacency_list.get(vertex, [])

    def print_graph(self):
        for vertex, neighbors in self.adjacency_list.items():
            print(f"{vertex} → {neighbors}")

g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
g.print_graph()

print(g.has_edge('A', 'B'))  # True
print(g.has_edge('A', 'E'))  # False

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjacencyList;

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

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

    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);
        adjacencyList.get(v1).add(v2);
        adjacencyList.get(v2).add(v1); // remove for directed
    }

    public boolean hasEdge(String v1, String v2) {
        return adjacencyList.getOrDefault(v1, Collections.emptyList()).contains(v2);
    }

    public List<String> getNeighbors(String vertex) {
        return adjacencyList.getOrDefault(vertex, Collections.emptyList());
    }

    public void printGraph() {
        for (var entry : adjacencyList.entrySet()) {
            System.out.println(entry.getKey() + " → " + entry.getValue());
        }
    }

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

        System.out.println(g.hasEdge("A", "B"));  // true
        System.out.println(g.hasEdge("A", "E"));  // false
    }
}

Adjacency Matrix

class GraphMatrix {
  constructor(vertices) {
    this.vertices = vertices;
    this.index = {};
    vertices.forEach((v, i) => this.index[v] = i);
    this.matrix = Array.from({ length: vertices.length },
      () => Array(vertices.length).fill(0));
  }

  addEdge(v1, v2) {
    const i = this.index[v1], j = this.index[v2];
    this.matrix[i][j] = 1;
    this.matrix[j][i] = 1; // remove for directed
  }

  hasEdge(v1, v2) {
    return this.matrix[this.index[v1]][this.index[v2]] === 1;
  }

  getNeighbors(vertex) {
    const i = this.index[vertex];
    return this.vertices.filter((_, j) => this.matrix[i][j] === 1);
  }

  print() {
    console.log('   ' + this.vertices.join('  '));
    for (let i = 0; i < this.vertices.length; i++) {
      console.log(this.vertices[i] + ' [' + this.matrix[i].join(', ') + ']');
    }
  }
}

const g = new GraphMatrix(['A', 'B', 'C', 'D', 'E']);
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
g.addEdge('C', 'D');
g.addEdge('D', 'E');
g.print();
console.log(g.hasEdge('A', 'B'));     // true
console.log(g.getNeighbors('D'));     // ['B', 'C', 'E']

class GraphMatrix:
    def __init__(self, vertices):
        self.vertices = vertices
        self.index = {v: i for i, v in enumerate(vertices)}
        self.matrix = [[0] * len(vertices) for _ in range(len(vertices))]

    def add_edge(self, v1, v2):
        i, j = self.index[v1], self.index[v2]
        self.matrix[i][j] = 1
        self.matrix[j][i] = 1  # remove for directed

    def has_edge(self, v1, v2):
        return self.matrix[self.index[v1]][self.index[v2]] == 1

    def get_neighbors(self, vertex):
        i = self.index[vertex]
        return [v for j, v in enumerate(self.vertices) if self.matrix[i][j] == 1]

    def print_graph(self):
        print('   ' + '  '.join(self.vertices))
        for i, v in enumerate(self.vertices):
            print(f"{v} {self.matrix[i]}")

g = GraphMatrix(['A', 'B', 'C', 'D', 'E'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
g.print_graph()
print(g.has_edge('A', 'B'))     # True
print(g.get_neighbors('D'))     # ['B', 'C', 'E']

public class GraphMatrix {
    private String[] vertices;
    private int[][] matrix;
    private Map<String, Integer> index;

    public GraphMatrix(String[] vertices) {
        this.vertices = vertices;
        this.matrix = new int[vertices.length][vertices.length];
        this.index = new HashMap<>();
        for (int i = 0; i < vertices.length; i++) {
            index.put(vertices[i], i);
        }
    }

    public void addEdge(String v1, String v2) {
        int i = index.get(v1), j = index.get(v2);
        matrix[i][j] = 1;
        matrix[j][i] = 1; // remove for directed
    }

    public boolean hasEdge(String v1, String v2) {
        return matrix[index.get(v1)][index.get(v2)] == 1;
    }

    public List<String> getNeighbors(String vertex) {
        int i = index.get(vertex);
        List<String> neighbors = new ArrayList<>();
        for (int j = 0; j < vertices.length; j++) {
            if (matrix[i][j] == 1) neighbors.add(vertices[j]);
        }
        return neighbors;
    }

    public static void main(String[] args) {
        GraphMatrix g = new GraphMatrix(
            new String[]{"A", "B", "C", "D", "E"});
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "D");
        g.addEdge("C", "D");
        g.addEdge("D", "E");

        System.out.println(g.hasEdge("A", "B"));     // true
        System.out.println(g.getNeighbors("D"));     // [B, C, E]
    }
}

Weighted graphs

For weighted edges, store the weight instead of just 1:

Weighted adjacency list

class WeightedGraph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2, weight) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push({ node: v2, weight });
    this.adjacencyList.get(v2).push({ node: v1, weight });
  }
}

const g = new WeightedGraph();
g.addEdge('A', 'B', 4);
g.addEdge('A', 'C', 2);
g.addEdge('B', 'D', 3);
// A → [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }]

Weighted adjacency matrix

// Store weights instead of 0/1
// Use Infinity for no edge
const matrix = [
  //    A     B     C     D
  [    0,    4,    2,  Infinity], // A
  [    4,    0, Infinity,  3   ], // B
  [    2, Infinity, 0, Infinity], // C
  [Infinity, 3, Infinity,  0   ], // D
];

Weighted graphs are used in algorithms like Dijkstra’s shortest path, where edge weights represent distances or costs.

Directed graphs

In a directed graph (digraph), edges have a direction. The only change is that addEdge adds the connection in one direction only:

// Directed: A → B does NOT mean B → A
addEdge(from, to) {
  this.addVertex(from);
  this.addVertex(to);
  this.adjacencyList.get(from).push(to);
  // no reverse edge
}

For an adjacency matrix, matrix[i][j] = 1 means there’s an edge from i to j, but matrix[j][i] might be 0.

Adjacency list vs adjacency matrix

Operation	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Remove edge	O(E)	O(1)
Check edge exists	O(degree)	O(1)
Get all neighbors	O(degree)	O(V)
Add vertex	O(1)	O(V²) — rebuild matrix

Where V = vertices, E = edges, and degree = number of edges on a vertex.

When to use which

Adjacency list when:

The graph is sparse (E « V²) — most real-world graphs
You frequently iterate over a vertex’s neighbors
Memory matters

Adjacency matrix when:

The graph is dense (E ≈ V²)
You need fast O(1) edge existence checks
The vertex count is small and fixed

A graph with 10,000 vertices needs a 10,000 × 10,000 matrix (100 million entries). If it only has 50,000 edges, an adjacency list uses a fraction of that memory.

Edge list

A third, simpler representation — just store edges as pairs:

const edges = [
  ['A', 'B'],
  ['A', 'C'],
  ['B', 'D'],
  ['C', 'D'],
  ['D', 'E'],
];

// Weighted version
const weightedEdges = [
  ['A', 'B', 4],
  ['A', 'C', 2],
  ['B', 'D', 3],
];

Edge lists are compact and useful for algorithms like Kruskal’s minimum spanning tree that process edges directly. But checking if a specific edge exists requires scanning the entire list — O(E).

Complexity summary

Representation	Space	Check Edge	Get Neighbors	Add Edge
Adjacency List	O(V + E)	O(degree)	O(degree)	O(1)
Adjacency Matrix	O(V²)	O(1)	O(V)	O(1)
Edge List	O(E)	O(E)	O(E)	O(1)

Choose your representation based on the operations your algorithm needs most. For BFS and DFS, adjacency lists are almost always the right choice since both algorithms iterate over neighbors repeatedly.

Table of Contents