Graph Representations (Adjacency Matrix, Adjacency List)

Pick a representation based on graph density, operations, and memory.

Adjacency Matrix

N×N boolean/weight grid
Edge check O(1), iterate neighbors O(N) per vertex
Space O(N^2) even if few edges
Great for dense graphs, Floyd–Warshall, or bitset tricks

// Matrix (weights or Infinity for no edge)
const N = 4
const INF = 1e15
const mat = Array.from({ length: N }, () => Array(N).fill(INF))
for (let i=0;i<N;i++) mat[i][i]=0
function addDirected(u,v,w=1){ mat[u][v]=w }

Adjacency List

Array/map of neighbor lists: adj[u] = [v1, v2, ...] or weighted adjW[u] = [[v,w], ...]
Edge check O(deg(u)), iterate neighbors O(deg(u))
Space O(N + M) for N vertices and M edges
Excellent for sparse graphs and most traversals

// Unweighted undirected
const N = 5
const adj = Array.from({ length: N }, () => [])
function addUndirected(u, v) { adj[u].push(v); adj[v].push(u) }

Edge List

Just a list of edges [[u,v,w], ...]
Minimal overhead; sort/filter-friendly (e.g., Kruskal)
Convert to matrix/list as needed for traversal

const edges = []
function addEdge(u,v,w=1){ edges.push([u,v,w]) }

Conversions and Tips

Matrix → List: scan rows to collect neighbors in O(N^2)
List → Matrix: fill grid in O(N + M)
For directed graphs, only add one direction; for undirected, add both
Weighted graphs: store pairs [v,w] or an object { v, w }
Self-loops and multi-edges: represent explicitly if needed

Sparse graphs favor adjacency lists; dense graphs may favor matrices. For algorithms dominated by neighbor iteration (BFS, DFS), lists usually win.