🕸️ JavaScript Graph Basics

Graph Representations

Adjacency List (Most Common)

// Undirected graph
const graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1],
    4: [2],
};

// Using Map
const graphMap = new Map();
graphMap.set(0, [1, 2]);
graphMap.set(1, [0, 3]);

Build Graph from Edge List

function buildGraph(n, edges, directed = false) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        if (!directed) graph[v].push(u);
    }
    return graph;
}

Adjacency Matrix

const n = 4;
const matrix = Array.from({ length: n }, () => new Array(n).fill(0));
matrix[0][1] = 1; // 0 → 1
matrix[1][2] = 1; // 1 → 2

Adjacency list: O(V + E) space — preferred for sparse graphs. Adjacency matrix: O(V²) space — preferred for dense graphs or O(1) edge lookup.

---

Graph Terminology

---

Union-Find (Disjoint Set Union)

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank   = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]); // path compression
        return this.parent[x];
    }
    union(x, y) {
        const px = this.find(x), py = this.find(y);
        if (px === py) return false;
        if (this.rank[px] < this.rank[py]) [this.parent[px], this.parent[py]] = [py, px];
        else { this.parent[py] = px; if (this.rank[px] === this.rank[py]) this.rank[px]++; }
        return true;
    }
    connected(x, y) { return this.find(x) === this.find(y); }
}

Time: O(α(n)) ≈ O(1) per operation | Space: O(n)

---

Complexity Summary