Graphs

A graph is the most general relational structure in computing: a set of vertices (nodes) connected by edges (relationships). Almost everything models as a graph — road networks, social follows, package dependencies, web links, state machines. Trees and linked lists are just special, restricted graphs.

What makes graphs feel harder than trees is that they carry no built-in shape: an edge can point back to an ancestor, form a cycle, or leave a node stranded with no connections at all. Before you can run any algorithm on one, you have to answer a practical question — how do I store the edges? That single choice drives every later trade-off.

The vocabulary

• Directed vs undirected: a directed edge u → v is one-way (a Twitter follow); an undirected edge u — v goes both ways (a Facebook friendship).
• Weighted vs unweighted: a weighted edge carries a number — distance, cost, capacity. Unweighted edges are all equal, so "shortest" means fewest hops.
• Degree: how many edges touch a vertex. Directed graphs split this into in-degree (edges arriving) and out-degree (edges leaving).
• Cycle: a path that returns to its start. A graph with no cycles and a direction is a DAG — the shape behind build systems and task scheduling.

Representation 1 — Adjacency list

Store, for each vertex, a list of its neighbours. This is the default representation for most problems because real-world graphs are sparse (far fewer edges than the V² maximum), and a list only spends memory on edges that actually exist.

class Graph {
  constructor(directed = false) {
    this.adj = new Map()
    this.directed = directed
  }
  addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, [])
  }
  addEdge(u, v, weight = 1) {
    this.addVertex(u); this.addVertex(v)
    this.adj.get(u).push({ node: v, weight })
    if (!this.directed) this.adj.get(v).push({ node: u, weight })
  }
  neighbors(v) {
    return this.adj.get(v) ?? []
  }
}

Representation 2 — Adjacency matrix

Store a V×V grid where matrix[u][v] holds the edge weight (or 0 / Infinity for "no edge"). Checking whether two specific vertices are connected is instant, O(1) — but you pay O(V²) memory whether the graph is dense or nearly empty.

class MatrixGraph {
  constructor(n, directed = false) {
    this.n = n
    this.directed = directed
    this.m = Array.from({ length: n }, () => Array(n).fill(0))
  }
  addEdge(u, v, weight = 1) {
    this.m[u][v] = weight
    if (!this.directed) this.m[v][u] = weight
  }
  hasEdge(u, v) {
    return this.m[u][v] !== 0    // O(1) lookup
  }
}