Graph Representation Techniques

What Is Graph Representation?

A graph is a data structure made up of vertices (also called nodes) and edges that connect those vertices. Before a graph can be processed by an algorithm, it needs to be stored in a form that a program can work with efficiently.

Graph representation refers to the way vertices and edges are stored in memory. The representation you choose affects memory usage, edge lookup speed, traversal performance, and the complexity of common graph operations.

The most common graph representations are:

• Adjacency matrix
• Adjacency list
• Edge list

A Simple Graph Example

Consider a graph containing four vertices and four edges:

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

Its vertices are:

A, B, C, D

Its edges are:

(A, B)
(A, C)
(B, D)
(C, D)

The same graph can be represented in several different ways depending on the operations the application needs to perform.

1. Adjacency Matrix

An adjacency matrix uses a two-dimensional matrix to represent connections between vertices. If a graph contains V vertices, the matrix has V × V positions.

For an unweighted graph, a value such as 1 can indicate that an edge exists, while 0 indicates that no edge exists.

    A  B  C  D
A   0  1  1  0
B   1  0  0  1
C   1  0  0  1
D   0  1  1  0

For example, the value at row A and column B is 1, meaning A and B are connected. The value at row A and column D is 0, meaning there is no direct edge between them.

Creating an Adjacency Matrix in JavaScript

const graph = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0]
];

console.log(graph[0][1]); // 1
console.log(graph[0][3]); // 0

Matrix access is direct, so checking whether two vertices are connected takes O(1) time.

2. Adjacency List

An adjacency list stores the neighbors of each vertex. Instead of allocating space for every possible pair of vertices, it stores only the connections that actually exist.

The example graph can be represented as:

A → B, C
B → A, D
C → A, D
D → B, C

Adjacency List with JavaScript

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

console.log(graph.A); // ['B', 'C']

JavaScript objects or Map can be used to store adjacency lists. A Map is particularly useful when vertex identifiers are not limited to simple object property keys.

const graph = new Map();

graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A', 'D']);
graph.set('D', ['B', 'C']);

console.log(graph.get('A')); // ['B', 'C']

3. Edge List

An edge list stores the graph as a collection of edges. Each edge contains the vertices that it connects.

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

Edge lists are simple and useful when an algorithm primarily needs to process every edge. They are especially common in algorithms involving sorting or examining edges, such as minimum spanning tree algorithms.

Weighted Graph Representation

Graphs can contain weights on their edges. A weight might represent distance, cost, time, bandwidth, or another numerical value.

For example:

A ---- 5 ---- B
|              |
2              3
|              |
C ---- 4 ---- D

An adjacency matrix can store the weight instead of simply storing 1.

    A  B  C  D
A   0  5  2  0
B   5  0  0  3
C   2  0  0  4
D   0  3  4  0

An adjacency list can store each neighbor together with its edge weight:

const graph = {
  A: [
    { node: 'B', weight: 5 },
    { node: 'C', weight: 2 }
  ],
  B: [
    { node: 'A', weight: 5 },
    { node: 'D', weight: 3 }
  ],
  C: [
    { node: 'A', weight: 2 },
    { node: 'D', weight: 4 }
  ],
  D: [
    { node: 'B', weight: 3 },
    { node: 'C', weight: 4 }
  ]
};

Directed Graph Representation

In a directed graph, an edge has a direction. An edge from A to B does not automatically mean that B has an edge back to A.

A → B
↓
C → D

An adjacency list for this graph could be:

const graph = {
  A: ['B', 'C'],
  B: [],
  C: ['D'],
  D: []
};

For an undirected graph, adding an edge usually means adding the relationship in both directions. For a directed graph, only the specified direction is stored.

Adjacency Matrix vs Adjacency List

The choice between a matrix and a list depends largely on the density of the graph and the operations that need to be performed.

Graph Density and Representation Choice

The number of edges relative to the number of possible edges is an important factor when selecting a graph representation.

A dense graph has many edges connecting its vertices. An adjacency matrix can be useful because much of the matrix contains meaningful connections.

A sparse graph has relatively few edges. An adjacency list generally saves memory because it stores only the existing connections instead of reserving space for every possible pair.

Building an Adjacency List Dynamically

In practical applications, vertices and edges are often added dynamically. The following class provides a simple undirected graph implementation using an adjacency list.

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

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

  addEdge(vertexA, vertexB) {
    this.addVertex(vertexA);
    this.addVertex(vertexB);

    this.adjacencyList.get(vertexA).push(vertexB);
    this.adjacencyList.get(vertexB).push(vertexA);
  }

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

const graph = new Graph();

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'D');

console.log(graph.getNeighbors('A'));
console.log(graph.getNeighbors('D'));

Using Graph Representations in Algorithms

Graph algorithms interact with the representation in different ways. Breadth-First Search and Depth-First Search commonly benefit from adjacency lists because they need to examine the neighbors of each vertex.

Algorithms that frequently ask whether a particular edge exists can benefit from the constant-time lookup provided by an adjacency matrix.

Edge-oriented algorithms may work naturally with an edge list because each edge is already stored as an independent record.

Choosing the Right Graph Representation

• Use an adjacency matrix when fast direct edge lookup is important.
• Use an adjacency list when the graph is sparse or neighbor traversal is common.
• Use an edge list when algorithms primarily process edges.
• Use weighted adjacency structures when edge costs or distances must be stored.
• Use directed representations when relationships have a specific direction.
• Consider memory requirements when the graph contains a large number of vertices.

Common Mistakes

• Forgetting that an undirected edge normally needs to appear in both adjacency lists.
• Accidentally treating a directed graph as undirected.
• Using an adjacency matrix for a very large sparse graph without considering memory usage.
• Ignoring edge weights when implementing weighted graph algorithms.
• Confusing vertices with edges when calculating graph complexity.
• Assuming that every graph algorithm performs equally well with every representation.

Key Takeaways

• Graph representation determines how vertices and edges are stored in memory.
• Adjacency matrices use O(V²) space and provide constant-time direct edge lookup.
• Adjacency lists use O(V + E) space and are efficient for traversing neighbors.
• Edge lists store each edge directly and are useful for edge-oriented algorithms.
• Weighted graphs store additional values such as distance or cost with their edges.
• Graph density and the operations required by an algorithm should guide the representation choice.