Data Structures & AlgorithmsGraph Representation — Adjacency Matrix

Graph Representation — Adjacency Matrix

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency Matrix

1 / 4

2D Array Representation

From Graph Abstraction to Concrete Data

In the previous modules, we established graphs as the most general structure for representing relationships between entities. We explored vertices, edges, directed and undirected connections, and weighted edges. But all of that was abstract—mathematical notation on paper.

Now we face a critical question every engineer must answer: How do we actually store a graph in computer memory?

This question isn't merely academic. The choice of graph representation profoundly affects every algorithm you'll run on the graph. It determines memory consumption, the speed of common operations, and even which algorithms are practical to implement. Get this choice wrong, and you'll watch your graph algorithms crawl on datasets that should be handled easily.

In this module, we'll master the first and most elegant representation: the adjacency matrix—a simple yet powerful approach that encodes the entire graph structure in a two-dimensional array.

What You Will Learn

By the end of this page, you will deeply understand how to represent any graph as a 2D array, how the matrix structure maps to graph concepts, and how to construct adjacency matrices for directed, undirected, and weighted graphs. You'll be able to visualize the connection between the abstract graph and its matrix representation with complete clarity.

The Fundamental Insight: Relationships as Grid Cells

The adjacency matrix representation is built on a beautifully simple insight: if we have V vertices, we can represent all possible edges between them using a V × V grid.

Think about it this way. If you have 5 people at a party and want to track who has shaken hands with whom, you could create a 5×5 grid. Each row represents a person, each column represents a person, and the cell at row i, column j indicates whether person i has shaken hands with person j.

This is precisely what an adjacency matrix does for graphs. Every possible connection between any two vertices has a dedicated cell in the matrix. If the edge exists, we mark it (typically with 1 or the edge weight). If it doesn't exist, we use 0 or a special 'no edge' value.

Why 'Adjacency' Matrix?

The term 'adjacency' refers to the fact that two vertices are adjacent if there's an edge directly connecting them. The matrix answers the adjacency question: for any pair of vertices (i, j), are they adjacent? The answer is stored at position matrix[i][j].

Formal Definition:

For a graph G = (V, E) with vertices numbered 0 to V-1, the adjacency matrix A is a V × V matrix where:

For an unweighted graph: A[i][j] = 1 if there's an edge from vertex i to vertex j, and A[i][j] = 0 otherwise.
For a weighted graph: A[i][j] = w (the edge weight) if there's an edge from i to j with weight w, and A[i][j] = 0 (or ∞, or a sentinel value) if no edge exists.

This simple definition encapsulates the entire graph structure in a single data structure. The matrix IS the graph—every edge, every non-edge, completely encoded.

Matrix Construction for Undirected Graphs

Let's build intuition by constructing an adjacency matrix step by step. Consider a simple undirected graph with 5 vertices (0, 1, 2, 3, 4) and the following edges:

0 — 1
0 — 2
1 — 2
1 — 3
2 — 4
3 — 4

Step 1: Create the empty V × V matrix

We initialize a 5×5 matrix filled with zeros. Each row represents a 'from' vertex, each column represents a 'to' vertex.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Initial empty matrix (all zeros):
 
     0   1   2   3   4   ← Column indices (destination vertices)
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 1 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 2 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 0 │ 0 │ 0 │
   └───┴───┴───┴───┴───┘
 ↑
Row indices (source vertices)

Step 2: Add each edge by setting TWO cells

For an undirected graph, each edge is bidirectional. The edge 0—1 means both 'vertex 0 connects to vertex 1' AND 'vertex 1 connects to vertex 0'. Therefore, we set BOTH matrix[0][1] = 1 AND matrix[1][0] = 1.

This produces a symmetric matrix—a critical property of adjacency matrices for undirected graphs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
After adding edge 0—1 (set [0][1] and [1][0]):
 
     0   1   2   3   4
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 1 │ 0 │ 0 │ 0 │  ← Row 0: vertex 0 connects to vertex 1
   ├───┼───┼───┼───┼───┤
 1 │ 1 │ 0 │ 0 │ 0 │ 0 │  ← Row 1: vertex 1 connects to vertex 0
   ├───┼───┼───┼───┼───┤
 2 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 0 │ 0 │ 0 │
   └───┴───┴───┴───┴───┘

Step 3: Continue with remaining edges

Following the same process for all edges:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Final adjacency matrix for the undirected graph:
 
     0   1   2   3   4
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 1 │ 1 │ 0 │ 0 │  ← Vertex 0 connects to: 1, 2
   ├───┼───┼───┼───┼───┤
 1 │ 1 │ 0 │ 1 │ 1 │ 0 │  ← Vertex 1 connects to: 0, 2, 3
   ├───┼───┼───┼───┼───┤
 2 │ 1 │ 1 │ 0 │ 0 │ 1 │  ← Vertex 2 connects to: 0, 1, 4
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 1 │ 0 │ 0 │ 1 │  ← Vertex 3 connects to: 1, 4
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 1 │ 1 │ 0 │  ← Vertex 4 connects to: 2, 3
   └───┴───┴───┴───┴───┘
 
Notice: The matrix is symmetric along the main diagonal.
        A[i][j] = A[j][i] for all i, j — this is always true
        for undirected graphs.

Visual Symmetry Check

An easy way to verify correctness for undirected graphs: fold the matrix along the main diagonal (top-left to bottom-right). Both halves should match perfectly. If they don't, you've made an error or you're working with a directed graph.

Matrix Construction for Directed Graphs

Directed graphs (digraphs) have edges with direction—an edge from vertex i to vertex j does NOT imply an edge from j to i. This changes how we construct the adjacency matrix.

Consider a directed graph with 4 vertices (0, 1, 2, 3) and edges:

0 → 1
0 → 2
1 → 2
2 → 0
2 → 3
3 → 3 (a self-loop)

For directed graphs, we only set ONE cell per edge: For an edge from i to j, we set A[i][j] = 1. We do NOT automatically set A[j][i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Directed graph adjacency matrix:
 
     0   1   2   3
   ┌───┬───┬───┬───┐
 0 │ 0 │ 1 │ 1 │ 0 │  ← From 0: edges go TO 1, TO 2
   ├───┼───┼───┼───┤
 1 │ 0 │ 0 │ 1 │ 0 │  ← From 1: edge goes TO 2
   ├───┼───┼───┼───┤
 2 │ 1 │ 0 │ 0 │ 1 │  ← From 2: edges go TO 0, TO 3
   ├───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 1 │  ← From 3: self-loop (goes TO itself)
   └───┴───┴───┴───┘
 
Notice: The matrix is NOT symmetric.
        The '1' at [2][0] represents edge 2→0, but there's
        no '1' at [0][2] for edge 0→2 wait... actually there IS
        an edge 0→2, so [0][2]=1. Let me re-verify...
 
Correction: [0][2]=1 (edge 0→2 exists), [2][0]=1 (edge 2→0 exists)
These are two DIFFERENT edges, both present in this graph.

Reading Convention (Critical!):

The standard convention is:

Row index = source vertex (FROM)
Column index = destination vertex (TO)

So A[i][j] = 1 means there's an edge FROM i TO j.

To find all outgoing edges from vertex i: scan row i (all columns). To find all incoming edges to vertex j: scan column j (all rows).

This convention is nearly universal, but always verify when reading graph code—some implementations flip the convention.

Self-Loops Appear on the Diagonal

A self-loop (an edge from a vertex to itself) is represented on the main diagonal. In our example, the self-loop 3→3 appears as A[3][3] = 1. For undirected graphs, self-loops contribute to the diagonal but are typically rare in most applications.

Weighted Graph Matrices

For weighted graphs, instead of storing 1 for 'edge exists', we store the edge weight in the corresponding cell. But this introduces a nuance: how do we distinguish between 'no edge' and 'edge with weight 0'?

Common Approaches:

Use a sentinel value — Store a special value like ∞ (infinity), -1, or null to indicate no edge. This is the most common approach.
Separate existence matrix — Maintain two matrices: one for adjacency (0/1), one for weights. More memory but no ambiguity.
Assume non-negative weights — If all weights are positive, use 0 or negative values for 'no edge'. Works, but limits the graphs you can represent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Weighted directed graph example:
 
Edges with weights:
  0 → 1 (weight 5)
  0 → 2 (weight 3)
  1 → 2 (weight 2)
  1 → 3 (weight 8)
  2 → 3 (weight 1)
 
Adjacency matrix (using ∞ for no edge):
 
       0     1     2     3
    ┌─────┬─────┬─────┬─────┐
  0 │  ∞  │  5  │  3  │  ∞  │
    ├─────┼─────┼─────┼─────┤
  1 │  ∞  │  ∞  │  2  │  8  │
    ├─────┼─────┼─────┼─────┤
  2 │  ∞  │  ∞  │  ∞  │  1  │
    ├─────┼─────┼─────┼─────┤
  3 │  ∞  │  ∞  │  ∞  │  ∞  │
    └─────┴─────┴─────┴─────┘
 
The shortest path from 0 to 3 is: 0 → 2 → 3 with total weight 4
(We'll learn algorithms to compute this in later chapters!)

Infinity in Practice

In code, infinity is typically represented as MAX_INT, MAX_FLOAT, or a language-specific infinity constant. In Python: float('inf'). In JavaScript: Infinity. In Java: Integer.MAX_VALUE. Choose a value larger than any possible path weight to avoid algorithmic confusion.

Weighted Undirected Graphs:

For weighted undirected graphs, the matrix remains symmetric—both A[i][j] and A[j][i] store the same edge weight. An edge between vertices 0 and 1 with weight 5 means A[0][1] = A[1][0] = 5.

This symmetry property halves the information content (redundant storage), which we'll discuss in the space complexity section. For now, recognize that weighted undirected graphs follow the same symmetry rules as unweighted ones.

Implementation in Code

Let's translate these concepts into working code. We'll implement a complete adjacency matrix class that handles both weighted and unweighted graphs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**
 * Adjacency Matrix representation of a graph.
 * Supports both weighted and unweighted, directed and undirected graphs.
 */
class AdjacencyMatrix {
    private matrix: number[][];
    private vertices: number;
    private isDirected: boolean;
    private noEdgeValue: number;  // Sentinel for "no edge"
 
    /**
     * Create a new adjacency matrix.
     * @param vertices - Number of vertices in the graph
     * @param isDirected - Whether edges are directed
     * @param noEdgeValue - Value representing "no edge" (default: 0)
     */
    constructor(
        vertices: number,
        isDirected: boolean = false,
        noEdgeValue: number = 0
    ) {
        this.vertices = vertices;
        this.isDirected = isDirected;
        this.noEdgeValue = noEdgeValue;
 
        // Initialize V × V matrix with "no edge" values
        // This is the O(V²) space allocation that defines this representation
        this.matrix = Array.from(
            { length: vertices },
            () => Array(vertices).fill(noEdgeValue)
        );
    }
 
    /**
     * Add an edge between two vertices.
     * For unweighted graphs, weight defaults to 1.
     * For undirected graphs, adds edge in both directions.
     * 
     * Time complexity: O(1) - direct array access
     */
    addEdge(from: number, to: number, weight: number = 1): void {
        this.validateVertex(from);
        this.validateVertex(to);
 
        this.matrix[from][to] = weight;
 
        // For undirected graphs, add the reverse edge
        if (!this.isDirected) {
            this.matrix[to][from] = weight;
        }
    }
 
    /**
     * Remove an edge between two vertices.
     * Time complexity: O(1)
     */
    removeEdge(from: number, to: number): void {
        this.validateVertex(from);
        this.validateVertex(to);
 
        this.matrix[from][to] = this.noEdgeValue;
 
        if (!this.isDirected) {
            this.matrix[to][from] = this.noEdgeValue;
        }
    }
 
    /**
     * Check if an edge exists between two vertices.
     * Time complexity: O(1) - THIS is the key advantage!
     */
    hasEdge(from: number, to: number): boolean {
        this.validateVertex(from);
        this.validateVertex(to);
 
        return this.matrix[from][to] !== this.noEdgeValue;
    }
 
    /**
     * Get the weight of an edge (returns noEdgeValue if no edge).
     * Time complexity: O(1)
     */
    getEdgeWeight(from: number, to: number): number {
        this.validateVertex(from);
        this.validateVertex(to);
 
        return this.matrix[from][to];
    }
 
    /**
     * Get all neighbors of a vertex.
     * Time complexity: O(V) - must scan entire row
     */
    getNeighbors(vertex: number): number[] {
        this.validateVertex(vertex);
 
        const neighbors: number[] = [];
        for (let j = 0; j < this.vertices; j++) {
            if (this.matrix[vertex][j] !== this.noEdgeValue) {
                neighbors.push(j);
            }
        }
        return neighbors;
    }
 
    /**
     * Get the degree of a vertex (number of edges).
     * For directed graphs, this is the out-degree.
     * Time complexity: O(V)
     */
    getDegree(vertex: number): number {
        return this.getNeighbors(vertex).length;
    }
 
    /**
     * For directed graphs: get in-degree (edges coming IN).
     * Time complexity: O(V) - must scan entire column
     */
    getInDegree(vertex: number): number {
        if (!this.isDirected) {
            return this.getDegree(vertex);
        }
 
        this.validateVertex(vertex);
 
        let inDegree = 0;
        for (let i = 0; i < this.vertices; i++) {
            if (this.matrix[i][vertex] !== this.noEdgeValue) {
                inDegree++;
            }
        }
        return inDegree;
    }
 
    /**
     * Print the matrix for visualization.
     */
    print(): void {
        console.log("Adjacency Matrix:");
        console.log("   " + [...Array(this.vertices).keys()].join("  "));
        for (let i = 0; i < this.vertices; i++) {
            const row = this.matrix[i].map(v => 
                v === Infinity ? "∞" : v.toString()
            ).join("  ");
            console.log(`${i}: ${row}`);
        }
    }
 
    private validateVertex(v: number): void {
        if (v < 0 || v >= this.vertices) {
            throw new Error(`Vertex ${v} is out of bounds [0, ${this.vertices - 1}]`);
        }
    }
}

Usage Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Create an undirected unweighted graph
const undirectedGraph = new AdjacencyMatrix(5, false);
undirectedGraph.addEdge(0, 1);  // Adds both 0→1 and 1→0
undirectedGraph.addEdge(0, 2);
undirectedGraph.addEdge(1, 3);
undirectedGraph.addEdge(2, 4);
 
console.log(undirectedGraph.hasEdge(0, 1));  // true
console.log(undirectedGraph.hasEdge(1, 0));  // true (symmetric!)
console.log(undirectedGraph.hasEdge(0, 4));  // false
 
// Create a directed weighted graph
const directedGraph = new AdjacencyMatrix(4, true, Infinity);
directedGraph.addEdge(0, 1, 5);   // 0→1 with weight 5
directedGraph.addEdge(0, 2, 3);   // 0→2 with weight 3
directedGraph.addEdge(1, 2, 2);   // 1→2 with weight 2
 
console.log(directedGraph.hasEdge(0, 1));  // true
console.log(directedGraph.hasEdge(1, 0));  // false (directed!)
console.log(directedGraph.getEdgeWeight(0, 1));  // 5
 
directedGraph.print();
// Output:
//    0  1  2  3
// 0: ∞  5  3  ∞
// 1: ∞  ∞  2  ∞
// 2: ∞  ∞  ∞  ∞
// 3: ∞  ∞  ∞  ∞

Initialization Matters

Note how we initialize the matrix with all 'no edge' values in the constructor. This is O(V²) work, but it only happens once. The alternative—checking for undefined on every access—would slow down all operations and complicate the code.

The Main Diagonal: Self-Loops and Self-Connections

The main diagonal of an adjacency matrix—the cells where row index equals column index (A[0][0], A[1][1], A[2][2], etc.)—represents self-loops: edges from a vertex to itself.

In many applications, self-loops are either:

Impossible by definition — A friendship network doesn't consider 'person is friends with themselves'
Implicitly true — Every vertex is 'reachable from itself' in zero steps
Meaningful data — A web page linking to itself, a state machine staying in the current state

Convention for the diagonal:

For most graphs: A[i][i] = 0 (no self-loops)
For adjacency matrices used in matrix algorithms (like finding paths of length k): A[i][i] = 0 usually
For reflexive relations or graphs with self-loops: A[i][i] = 1 or the self-loop weight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Adjacency matrix WITH self-loops:
 
       0     1     2     3
    ┌─────┬─────┬─────┬─────┐
  0 │  1  │  1  │  0  │  0  │  ← Self-loop at vertex 0
    ├─────┼─────┼─────┼─────┤
  1 │  1  │  0  │  1  │  0  │  ← No self-loop at vertex 1
    ├─────┼─────┼─────┼─────┤
  2 │  0  │  1  │  1  │  1  │  ← Self-loop at vertex 2
    ├─────┼─────┼─────┼─────┤
  3 │  0  │  0  │  1  │  0  │  ← No self-loop at vertex 3
    └─────┴─────┴─────┴─────┘
 
The main diagonal (highlighted cells) shows self-loops.

Diagonal and Undirected Graph Symmetry

For undirected graphs, the diagonal doesn't affect symmetry. If A[i][i] = 1 (self-loop exists), it's trivially symmetric since A[i][i] = A[i][i]. The symmetry constraint A[i][j] = A[j][i] specifically matters for off-diagonal elements.

Reading Graph Properties from the Matrix

One powerful aspect of the adjacency matrix is how naturally it expresses graph properties. Let's explore what we can read directly from the matrix structure:

Graph Properties from Adjacency Matrix
Property	How to Read from Matrix	Time Complexity
Edge existence	Check if A[i][j] ≠ 0 (or ≠ ∞)	O(1)
Out-degree of vertex i	Count non-zero entries in row i	O(V)
In-degree of vertex i	Count non-zero entries in column i	O(V)
Total edges (directed)	Count all non-zero entries	O(V²)
Total edges (undirected)	(Count non-zero entries) / 2	O(V²)
Is graph undirected?	Check if A[i][j] = A[j][i] for all i,j	O(V²)
Has self-loops?	Check if any A[i][i] ≠ 0	O(V)
Isolated vertices	Rows (and columns) that are entirely zero	O(V²)

Degree Sum Formula Verification:

Recall from graph theory: the sum of all vertex degrees equals twice the number of edges (for undirected graphs). With an adjacency matrix, this becomes: the sum of all entries in the matrix equals twice the edge count.

This provides a sanity check: if you add up every cell in an undirected graph's adjacency matrix and get an odd number, something is wrong—you've violated symmetry somewhere.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class AdjacencyMatrix {
    // ... (previous methods)
 
    /**
     * Count total edges in the graph.
     * For undirected graphs, edges are counted once (not double-counted).
     */
    countEdges(): number {
        let count = 0;
 
        for (let i = 0; i < this.vertices; i++) {
            // For undirected: only count upper triangle to avoid double-counting
            const startJ = this.isDirected ? 0 : i;
 
            for (let j = startJ; j < this.vertices; j++) {
                if (this.matrix[i][j] !== this.noEdgeValue) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    /**
     * Check if the graph is complete (every vertex connects to every other).
     * Time: O(V²)
     */
    isComplete(): boolean {
        for (let i = 0; i < this.vertices; i++) {
            for (let j = 0; j < this.vertices; j++) {
                // Skip self-loops
                if (i === j) continue;
 
                // If any non-diagonal entry is missing, not complete
                if (this.matrix[i][j] === this.noEdgeValue) {
                    return false;
                }
            }
        }
        return true;
    }
 
    /**
     * Find isolated vertices (no incoming or outgoing edges).
     * Time: O(V²)
     */
    findIsolatedVertices(): number[] {
        const isolated: number[] = [];
 
        for (let v = 0; v < this.vertices; v++) {
            let hasEdge = false;
 
            // Check outgoing (row)
            for (let j = 0; j < this.vertices; j++) {
                if (this.matrix[v][j] !== this.noEdgeValue) {
                    hasEdge = true;
                    break;
                }
            }
 
            // If no outgoing, check incoming (column) for directed graphs
            if (!hasEdge && this.isDirected) {
                for (let i = 0; i < this.vertices; i++) {
                    if (this.matrix[i][v] !== this.noEdgeValue) {
                        hasEdge = true;
                        break;
                    }
                }
            }
 
            if (!hasEdge) {
                isolated.push(v);
            }
        }
 
        return isolated;
    }
}

Summary: The 2D Array Representation

We've established a complete understanding of how graphs are represented using two-dimensional arrays. Let's consolidate the key concepts:

Key Takeaways

•An adjacency matrix is a V×V array where A[i][j] indicates the edge from vertex i to vertex j.
•Unweighted graphs use binary values — 1 for edge exists, 0 for no edge.
•Weighted graphs store edge weights — with a sentinel value (∞, -1, null) for no edge.
•Undirected graphs produce symmetric matrices — A[i][j] always equals A[j][i].
•Directed graphs may be asymmetric — edge i→j doesn't imply edge j→i.
•Self-loops appear on the main diagonal — A[i][i] ≠ 0 means vertex i has a self-loop.
•The matrix completely encodes the graph — every possible edge has a dedicated cell.

Coming up next:

Now that we understand how the matrix is structured, we'll analyze its space consumption in detail. Why does it require O(V²) space? When is this acceptable, and when is it prohibitive? The next page dives deep into the space complexity analysis and its implications.

Foundation Established

You now understand how to represent any graph as a 2D array. You can construct adjacency matrices for directed, undirected, weighted, and unweighted graphs. You know the convention (row = from, column = to) and can read graph properties directly from the matrix structure. This foundation prepares you for complexity analysis and algorithm implementation.

1 / 4

Loading learning content...

Data Structures & AlgorithmsGraph Representation — Adjacency Matrix

Graph Representation — Adjacency Matrix

LevelIntermediate

Duration60 mins

TopicGraph Representation — Adjacency Matrix

1 / 4

2D Array Representation

From Graph Abstraction to Concrete Data

Now we face a critical question every engineer must answer: How do we actually store a graph in computer memory?

In this module, we'll master the first and most elegant representation: the adjacency matrix—a simple yet powerful approach that encodes the entire graph structure in a two-dimensional array.

What You Will Learn

The Fundamental Insight: Relationships as Grid Cells

The adjacency matrix representation is built on a beautifully simple insight: if we have V vertices, we can represent all possible edges between them using a V × V grid.

Why 'Adjacency' Matrix?

Formal Definition:

For a graph G = (V, E) with vertices numbered 0 to V-1, the adjacency matrix A is a V × V matrix where:

For an unweighted graph: A[i][j] = 1 if there's an edge from vertex i to vertex j, and A[i][j] = 0 otherwise.
For a weighted graph: A[i][j] = w (the edge weight) if there's an edge from i to j with weight w, and A[i][j] = 0 (or ∞, or a sentinel value) if no edge exists.

This simple definition encapsulates the entire graph structure in a single data structure. The matrix IS the graph—every edge, every non-edge, completely encoded.

Matrix Construction for Undirected Graphs

Let's build intuition by constructing an adjacency matrix step by step. Consider a simple undirected graph with 5 vertices (0, 1, 2, 3, 4) and the following edges:

0 — 1
0 — 2
1 — 2
1 — 3
2 — 4
3 — 4

Step 1: Create the empty V × V matrix

We initialize a 5×5 matrix filled with zeros. Each row represents a 'from' vertex, each column represents a 'to' vertex.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Initial empty matrix (all zeros):
 
     0   1   2   3   4   ← Column indices (destination vertices)
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 1 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 2 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 0 │ 0 │ 0 │
   └───┴───┴───┴───┴───┘
 ↑
Row indices (source vertices)

Step 2: Add each edge by setting TWO cells

This produces a symmetric matrix—a critical property of adjacency matrices for undirected graphs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
After adding edge 0—1 (set [0][1] and [1][0]):
 
     0   1   2   3   4
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 1 │ 0 │ 0 │ 0 │  ← Row 0: vertex 0 connects to vertex 1
   ├───┼───┼───┼───┼───┤
 1 │ 1 │ 0 │ 0 │ 0 │ 0 │  ← Row 1: vertex 1 connects to vertex 0
   ├───┼───┼───┼───┼───┤
 2 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 0 │ 0 │ 0 │
   └───┴───┴───┴───┴───┘

Step 3: Continue with remaining edges

Following the same process for all edges:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Final adjacency matrix for the undirected graph:
 
     0   1   2   3   4
   ┌───┬───┬───┬───┬───┐
 0 │ 0 │ 1 │ 1 │ 0 │ 0 │  ← Vertex 0 connects to: 1, 2
   ├───┼───┼───┼───┼───┤
 1 │ 1 │ 0 │ 1 │ 1 │ 0 │  ← Vertex 1 connects to: 0, 2, 3
   ├───┼───┼───┼───┼───┤
 2 │ 1 │ 1 │ 0 │ 0 │ 1 │  ← Vertex 2 connects to: 0, 1, 4
   ├───┼───┼───┼───┼───┤
 3 │ 0 │ 1 │ 0 │ 0 │ 1 │  ← Vertex 3 connects to: 1, 4
   ├───┼───┼───┼───┼───┤
 4 │ 0 │ 0 │ 1 │ 1 │ 0 │  ← Vertex 4 connects to: 2, 3
   └───┴───┴───┴───┴───┘
 
Notice: The matrix is symmetric along the main diagonal.
        A[i][j] = A[j][i] for all i, j — this is always true
        for undirected graphs.

Visual Symmetry Check

Matrix Construction for Directed Graphs

Directed graphs (digraphs) have edges with direction—an edge from vertex i to vertex j does NOT imply an edge from j to i. This changes how we construct the adjacency matrix.

Consider a directed graph with 4 vertices (0, 1, 2, 3) and edges:

0 → 1
0 → 2
1 → 2
2 → 0
2 → 3
3 → 3 (a self-loop)

For directed graphs, we only set ONE cell per edge: For an edge from i to j, we set A[i][j] = 1. We do NOT automatically set A[j][i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Directed graph adjacency matrix:
 
     0   1   2   3
   ┌───┬───┬───┬───┐
 0 │ 0 │ 1 │ 1 │ 0 │  ← From 0: edges go TO 1, TO 2
   ├───┼───┼───┼───┤
 1 │ 0 │ 0 │ 1 │ 0 │  ← From 1: edge goes TO 2
   ├───┼───┼───┼───┤
 2 │ 1 │ 0 │ 0 │ 1 │  ← From 2: edges go TO 0, TO 3
   ├───┼───┼───┼───┤
 3 │ 0 │ 0 │ 0 │ 1 │  ← From 3: self-loop (goes TO itself)
   └───┴───┴───┴───┘
 
Notice: The matrix is NOT symmetric.
        The '1' at [2][0] represents edge 2→0, but there's
        no '1' at [0][2] for edge 0→2 wait... actually there IS
        an edge 0→2, so [0][2]=1. Let me re-verify...
 
Correction: [0][2]=1 (edge 0→2 exists), [2][0]=1 (edge 2→0 exists)
These are two DIFFERENT edges, both present in this graph.

Reading Convention (Critical!):

The standard convention is:

Row index = source vertex (FROM)
Column index = destination vertex (TO)

So A[i][j] = 1 means there's an edge FROM i TO j.

To find all outgoing edges from vertex i: scan row i (all columns). To find all incoming edges to vertex j: scan column j (all rows).

This convention is nearly universal, but always verify when reading graph code—some implementations flip the convention.

Self-Loops Appear on the Diagonal

Weighted Graph Matrices

Common Approaches:

Use a sentinel value — Store a special value like ∞ (infinity), -1, or null to indicate no edge. This is the most common approach.
Separate existence matrix — Maintain two matrices: one for adjacency (0/1), one for weights. More memory but no ambiguity.
Assume non-negative weights — If all weights are positive, use 0 or negative values for 'no edge'. Works, but limits the graphs you can represent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Weighted directed graph example:
 
Edges with weights:
  0 → 1 (weight 5)
  0 → 2 (weight 3)
  1 → 2 (weight 2)
  1 → 3 (weight 8)
  2 → 3 (weight 1)
 
Adjacency matrix (using ∞ for no edge):
 
       0     1     2     3
    ┌─────┬─────┬─────┬─────┐
  0 │  ∞  │  5  │  3  │  ∞  │
    ├─────┼─────┼─────┼─────┤
  1 │  ∞  │  ∞  │  2  │  8  │
    ├─────┼─────┼─────┼─────┤
  2 │  ∞  │  ∞  │  ∞  │  1  │
    ├─────┼─────┼─────┼─────┤
  3 │  ∞  │  ∞  │  ∞  │  ∞  │
    └─────┴─────┴─────┴─────┘
 
The shortest path from 0 to 3 is: 0 → 2 → 3 with total weight 4
(We'll learn algorithms to compute this in later chapters!)

Infinity in Practice

Weighted Undirected Graphs:

For weighted undirected graphs, the matrix remains symmetric—both A[i][j] and A[j][i] store the same edge weight. An edge between vertices 0 and 1 with weight 5 means A[0][1] = A[1][0] = 5.

Implementation in Code

Let's translate these concepts into working code. We'll implement a complete adjacency matrix class that handles both weighted and unweighted graphs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**
 * Adjacency Matrix representation of a graph.
 * Supports both weighted and unweighted, directed and undirected graphs.
 */
class AdjacencyMatrix {
    private matrix: number[][];
    private vertices: number;
    private isDirected: boolean;
    private noEdgeValue: number;  // Sentinel for "no edge"
 
    /**
     * Create a new adjacency matrix.
     * @param vertices - Number of vertices in the graph
     * @param isDirected - Whether edges are directed
     * @param noEdgeValue - Value representing "no edge" (default: 0)
     */
    constructor(
        vertices: number,
        isDirected: boolean = false,
        noEdgeValue: number = 0
    ) {
        this.vertices = vertices;
        this.isDirected = isDirected;
        this.noEdgeValue = noEdgeValue;
 
        // Initialize V × V matrix with "no edge" values
        // This is the O(V²) space allocation that defines this representation
        this.matrix = Array.from(
            { length: vertices },
            () => Array(vertices).fill(noEdgeValue)
        );
    }
 
    /**
     * Add an edge between two vertices.
     * For unweighted graphs, weight defaults to 1.
     * For undirected graphs, adds edge in both directions.
     * 
     * Time complexity: O(1) - direct array access
     */
    addEdge(from: number, to: number, weight: number = 1): void {
        this.validateVertex(from);
        this.validateVertex(to);
 
        this.matrix[from][to] = weight;
 
        // For undirected graphs, add the reverse edge
        if (!this.isDirected) {
            this.matrix[to][from] = weight;
        }
    }
 
    /**
     * Remove an edge between two vertices.
     * Time complexity: O(1)
     */
    removeEdge(from: number, to: number): void {
        this.validateVertex(from);
        this.validateVertex(to);
 
        this.matrix[from][to] = this.noEdgeValue;
 
        if (!this.isDirected) {
            this.matrix[to][from] = this.noEdgeValue;
        }
    }
 
    /**
     * Check if an edge exists between two vertices.
     * Time complexity: O(1) - THIS is the key advantage!
     */
    hasEdge(from: number, to: number): boolean {
        this.validateVertex(from);
        this.validateVertex(to);
 
        return this.matrix[from][to] !== this.noEdgeValue;
    }
 
    /**
     * Get the weight of an edge (returns noEdgeValue if no edge).
     * Time complexity: O(1)
     */
    getEdgeWeight(from: number, to: number): number {
        this.validateVertex(from);
        this.validateVertex(to);
 
        return this.matrix[from][to];
    }
 
    /**
     * Get all neighbors of a vertex.
     * Time complexity: O(V) - must scan entire row
     */
    getNeighbors(vertex: number): number[] {
        this.validateVertex(vertex);
 
        const neighbors: number[] = [];
        for (let j = 0; j < this.vertices; j++) {
            if (this.matrix[vertex][j] !== this.noEdgeValue) {
                neighbors.push(j);
            }
        }
        return neighbors;
    }
 
    /**
     * Get the degree of a vertex (number of edges).
     * For directed graphs, this is the out-degree.
     * Time complexity: O(V)
     */
    getDegree(vertex: number): number {
        return this.getNeighbors(vertex).length;
    }
 
    /**
     * For directed graphs: get in-degree (edges coming IN).
     * Time complexity: O(V) - must scan entire column
     */
    getInDegree(vertex: number): number {
        if (!this.isDirected) {
            return this.getDegree(vertex);
        }
 
        this.validateVertex(vertex);
 
        let inDegree = 0;
        for (let i = 0; i < this.vertices; i++) {
            if (this.matrix[i][vertex] !== this.noEdgeValue) {
                inDegree++;
            }
        }
        return inDegree;
    }
 
    /**
     * Print the matrix for visualization.
     */
    print(): void {
        console.log("Adjacency Matrix:");
        console.log("   " + [...Array(this.vertices).keys()].join("  "));
        for (let i = 0; i < this.vertices; i++) {
            const row = this.matrix[i].map(v => 
                v === Infinity ? "∞" : v.toString()
            ).join("  ");
            console.log(`${i}: ${row}`);
        }
    }
 
    private validateVertex(v: number): void {
        if (v < 0 || v >= this.vertices) {
            throw new Error(`Vertex ${v} is out of bounds [0, ${this.vertices - 1}]`);
        }
    }
}

Usage Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Create an undirected unweighted graph
const undirectedGraph = new AdjacencyMatrix(5, false);
undirectedGraph.addEdge(0, 1);  // Adds both 0→1 and 1→0
undirectedGraph.addEdge(0, 2);
undirectedGraph.addEdge(1, 3);
undirectedGraph.addEdge(2, 4);
 
console.log(undirectedGraph.hasEdge(0, 1));  // true
console.log(undirectedGraph.hasEdge(1, 0));  // true (symmetric!)
console.log(undirectedGraph.hasEdge(0, 4));  // false
 
// Create a directed weighted graph
const directedGraph = new AdjacencyMatrix(4, true, Infinity);
directedGraph.addEdge(0, 1, 5);   // 0→1 with weight 5
directedGraph.addEdge(0, 2, 3);   // 0→2 with weight 3
directedGraph.addEdge(1, 2, 2);   // 1→2 with weight 2
 
console.log(directedGraph.hasEdge(0, 1));  // true
console.log(directedGraph.hasEdge(1, 0));  // false (directed!)
console.log(directedGraph.getEdgeWeight(0, 1));  // 5
 
directedGraph.print();
// Output:
//    0  1  2  3
// 0: ∞  5  3  ∞
// 1: ∞  ∞  2  ∞
// 2: ∞  ∞  ∞  ∞
// 3: ∞  ∞  ∞  ∞

Initialization Matters

The Main Diagonal: Self-Loops and Self-Connections

The main diagonal of an adjacency matrix—the cells where row index equals column index (A[0][0], A[1][1], A[2][2], etc.)—represents self-loops: edges from a vertex to itself.

In many applications, self-loops are either:

Impossible by definition — A friendship network doesn't consider 'person is friends with themselves'
Implicitly true — Every vertex is 'reachable from itself' in zero steps
Meaningful data — A web page linking to itself, a state machine staying in the current state

Convention for the diagonal:

For most graphs: A[i][i] = 0 (no self-loops)
For adjacency matrices used in matrix algorithms (like finding paths of length k): A[i][i] = 0 usually
For reflexive relations or graphs with self-loops: A[i][i] = 1 or the self-loop weight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Adjacency matrix WITH self-loops:
 
       0     1     2     3
    ┌─────┬─────┬─────┬─────┐
  0 │  1  │  1  │  0  │  0  │  ← Self-loop at vertex 0
    ├─────┼─────┼─────┼─────┤
  1 │  1  │  0  │  1  │  0  │  ← No self-loop at vertex 1
    ├─────┼─────┼─────┼─────┤
  2 │  0  │  1  │  1  │  1  │  ← Self-loop at vertex 2
    ├─────┼─────┼─────┼─────┤
  3 │  0  │  0  │  1  │  0  │  ← No self-loop at vertex 3
    └─────┴─────┴─────┴─────┘
 
The main diagonal (highlighted cells) shows self-loops.

Diagonal and Undirected Graph Symmetry

Reading Graph Properties from the Matrix

One powerful aspect of the adjacency matrix is how naturally it expresses graph properties. Let's explore what we can read directly from the matrix structure:

Graph Properties from Adjacency Matrix
Property	How to Read from Matrix	Time Complexity
Edge existence	Check if A[i][j] ≠ 0 (or ≠ ∞)	O(1)
Out-degree of vertex i	Count non-zero entries in row i	O(V)
In-degree of vertex i	Count non-zero entries in column i	O(V)
Total edges (directed)	Count all non-zero entries	O(V²)
Total edges (undirected)	(Count non-zero entries) / 2	O(V²)
Is graph undirected?	Check if A[i][j] = A[j][i] for all i,j	O(V²)
Has self-loops?	Check if any A[i][i] ≠ 0	O(V)
Isolated vertices	Rows (and columns) that are entirely zero	O(V²)

Degree Sum Formula Verification:

This provides a sanity check: if you add up every cell in an undirected graph's adjacency matrix and get an odd number, something is wrong—you've violated symmetry somewhere.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class AdjacencyMatrix {
    // ... (previous methods)
 
    /**
     * Count total edges in the graph.
     * For undirected graphs, edges are counted once (not double-counted).
     */
    countEdges(): number {
        let count = 0;
 
        for (let i = 0; i < this.vertices; i++) {
            // For undirected: only count upper triangle to avoid double-counting
            const startJ = this.isDirected ? 0 : i;
 
            for (let j = startJ; j < this.vertices; j++) {
                if (this.matrix[i][j] !== this.noEdgeValue) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    /**
     * Check if the graph is complete (every vertex connects to every other).
     * Time: O(V²)
     */
    isComplete(): boolean {
        for (let i = 0; i < this.vertices; i++) {
            for (let j = 0; j < this.vertices; j++) {
                // Skip self-loops
                if (i === j) continue;
 
                // If any non-diagonal entry is missing, not complete
                if (this.matrix[i][j] === this.noEdgeValue) {
                    return false;
                }
            }
        }
        return true;
    }
 
    /**
     * Find isolated vertices (no incoming or outgoing edges).
     * Time: O(V²)
     */
    findIsolatedVertices(): number[] {
        const isolated: number[] = [];
 
        for (let v = 0; v < this.vertices; v++) {
            let hasEdge = false;
 
            // Check outgoing (row)
            for (let j = 0; j < this.vertices; j++) {
                if (this.matrix[v][j] !== this.noEdgeValue) {
                    hasEdge = true;
                    break;
                }
            }
 
            // If no outgoing, check incoming (column) for directed graphs
            if (!hasEdge && this.isDirected) {
                for (let i = 0; i < this.vertices; i++) {
                    if (this.matrix[i][v] !== this.noEdgeValue) {
                        hasEdge = true;
                        break;
                    }
                }
            }
 
            if (!hasEdge) {
                isolated.push(v);
            }
        }
 
        return isolated;
    }
}

Summary: The 2D Array Representation

We've established a complete understanding of how graphs are represented using two-dimensional arrays. Let's consolidate the key concepts:

Key Takeaways

•An adjacency matrix is a V×V array where A[i][j] indicates the edge from vertex i to vertex j.
•Unweighted graphs use binary values — 1 for edge exists, 0 for no edge.
•Weighted graphs store edge weights — with a sentinel value (∞, -1, null) for no edge.
•Undirected graphs produce symmetric matrices — A[i][j] always equals A[j][i].
•Directed graphs may be asymmetric — edge i→j doesn't imply edge j→i.
•Self-loops appear on the main diagonal — A[i][i] ≠ 0 means vertex i has a self-loop.
•The matrix completely encodes the graph — every possible edge has a dedicated cell.

Coming up next:

Foundation Established

1 / 4