Graphs Implementation — Adjacency List & Matrix Visualized
Learn graph representations — adjacency list vs adjacency matrix, space/time tradeoffs, interactive visualizer, and full Graph class implementation.
Introduction
Graph implementation choices affect every algorithm that follows. The two classic representations are adjacency list and adjacency matrix — each with different space and lookup tradeoffs.
Built on graph fundamentals, this post shows when to pick each.
Quick index
| # | Section |
|---|---|
| 1 | Two representations |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity comparison |
| 5 | Real-life examples |
1. Two representations
Adjacency list — each vertex stores its neighbors:
A → [B, C]
B → [A, D, E]
C → [A, F]Adjacency matrix — V×V grid where matrix[i][j] = 1 if edge exists:
A B C D E F
A [ 0 1 1 0 0 0 ]
B [ 1 0 0 1 1 0 ]
...2. Interactive visualizer
Graph Implementation — List vs Matrix
Adjacency list for sparse graphs; adjacency matrix for dense graphs and O(1) edge lookup.
Adjacency list
Each vertex stores its neighbors — space O(V + E), fast neighbor lookup.
Adjacency list
| class Graph { | |
| constructor() { this.adj = new Map() } | |
| addVertex(v) { if (!this.adj.has(v)) this.adj.set(v, []) } | |
| addEdge(a, b) { | |
| this.adj.get(a).push(b) | |
| this.adj.get(b).push(a) | undirected |
| } | |
| } |
Best for sparse graphs — most real-world networks.
List
O(V+E)
Matrix
O(V²)
Edge lookup
O(1) matrix
3. Full implementation
// ── Adjacency list (sparse graphs) ──
class GraphList {
constructor() {
this.adj = new Map()
this.vertices = []
}
addVertex(v) {
if (!this.adj.has(v)) {
this.adj.set(v, [])
this.vertices.push(v)
}
}
addEdge(a, b) {
this.addVertex(a)
this.addVertex(b)
this.adj.get(a).push(b)
this.adj.get(b).push(a)
}
getNeighbors(v) {
return this.adj.get(v) ?? []
}
hasEdge(a, b) {
return this.getNeighbors(a).includes(b)
}
}
// ── Adjacency matrix (dense graphs) ──
class GraphMatrix {
constructor(size) {
this.size = size
this.labels = []
this.matrix = Array.from({ length: size }, () => Array(size).fill(0))
}
addVertex(label) {
const i = this.labels.length
if (i >= this.size) throw new Error('Matrix full')
this.labels.push(label)
return i
}
addEdge(aIdx, bIdx) {
this.matrix[aIdx][bIdx] = 1
this.matrix[bIdx][aIdx] = 1
}
hasEdge(aIdx, bIdx) {
return this.matrix[aIdx][bIdx] === 1
}
}Function calls with output
// ── Demo calls — output shown on the right ──
const g = new GraphList()
g.addEdge('A', 'B')
g.addEdge('A', 'C')
g.addEdge('B', 'D')
g.getNeighbors('A') // → ['B', 'C']
g.getNeighbors('B') // → ['A', 'D']
g.hasEdge('A', 'C') // → true
g.hasEdge('C', 'D') // → false
const m = new GraphMatrix(4)
const a = m.addVertex('A') // → 0
const b = m.addVertex('B') // → 1
m.addEdge(a, b)
m.hasEdge(0, 1) // → true
m.hasEdge(0, 2) // → false4. Complexity comparison
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Add edge | O(1) | O(1) |
| Check edge | O(degree) | O(1) |
| List neighbors | O(degree) | O(V) |
5. Real-life examples
| System | Representation | Why |
|---|---|---|
| Adjacency list | Sparse — each user has limited connections | |
| Flight routes (small) | Adjacency matrix | Dense among hub airports, O(1) lookup |
| Neo4j | Adjacency list + index | Native graph DB stores edges per node |
| GPU mesh | Edge list / matrix | Dense local connectivity |
Flight route adjacency matrix
Airlines store direct routes in a matrix for O(1) "does a flight exist?" lookups between hub airports.
3 hubs → 3×3 adjacency matrix.
Real-world implementation
class RouteMatrix {
constructor(airports) {
this.labels = airports
const n = airports.length
this.matrix = Array.from({ length: n }, () => Array(n).fill(0))
}
addRoute(from, to) {
const i = this.labels.indexOf(from)
const j = this.labels.indexOf(to)
this.matrix[i][j] = 1
}
hasDirectRoute(from, to) {
return this.matrix[this.labels.indexOf(from)][this.labels.indexOf(to)] === 1
}
}Full working code for the scenario above.
Function calls with output
| // ── Function calls with output ── | |
| const routes = new RouteMatrix(["JFK","LHR","DXB"]) | → 3×3 matrix |
Side output shows return value after each call — step through to trace execution.
Summary
Pick adjacency list by default; use matrix when density or O(1) edge checks dominate.
Next reads: Graph Traversal · Cycle Detection
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime