Skip to content

04.GraphInJs.md

Latest commit

 

History

History
400 lines (260 loc) · 8.47 KB

04.GraphInJs.md

File metadata and controls

400 lines (260 loc) · 8.47 KB

Graph Representation in JavaScript - Adjacency Matrix, Adjacency List & Weighted Graphs 🧠📘

1. Quick problem statement & why representations matter

Problem statement (short): Given nodes and edges, choose a data structure to store the graph so algorithms (BFS, DFS, Dijkstra, MST, etc.) can run efficiently. Different representations change runtime, memory usage, and simplicity of implementation.

Why it matters:

  • Some algorithms iterate neighbors fast → adjacency list is great.
  • Some require O(1) edge-existence checks → adjacency matrix helps.
  • Weighted graphs need to store weights per edge.

Choosing the right representation is one of the easiest ways to improve performance.

2. Overview of common representations 🌉

  1. Adjacency Matrix - 2D array mat[u][v] indicates edge (or weight).
  2. Adjacency List - adj[u] = [v1, v2, ...].
  3. Edge List - [{u, v}] or [{u, v, w}] - useful for Kruskal and offline processing.

Rule of thumb:

  • Use adj list for sparse graphs (E ≈ V or E ≪ V²).
  • Use adj matrix for dense graphs (E ≈ V²) or when you need O(1) edge queries.
  • Use edge list when sorting edges or running offline algorithms.

3. Adjacency Matrix - explanation, pros/cons, code 🧾

What it is

An n × n 2D array where:

  • mat[u][v] = true/false for unweighted graphs
  • mat[u][v] = weight or Infinity for weighted graphs

Use-cases

  • Dense graphs
  • Fast O(1) hasEdge(u, v) checks
  • Simple educational examples

Memory & Complexity

  • Memory: O(n²)
  • Iterate neighbors of u: O(n)
  • Edge existence: O(1)

JavaScript Examples

Unweighted

const n = 5;
const mat = Array.from({ length: n }, () => Array(n).fill(false));

mat[u][v] = true;      // directed
mat[v][u] = true;      // undirected

const exists = mat[a][b];

Weighted

const INF = Infinity;
const mat = Array.from({ length: n }, () => Array(n).fill(INF));

for (let i = 0; i < n; i++) {
    mat[i][i] = 0;
}

mat[u][v] = weight;

Pitfalls

  • Huge memory usage for large n
  • Iterating neighbors always costs O(n) even if graph is sparse

4. Adjacency List - explanation, pros/cons, code 🌿

What it is

An array of arrays where each index stores its neighbors.

For weighted graphs: store objects like { to, weight }.

Use-cases

  • Most real-world graphs
  • Sparse graphs
  • Fast neighbor iteration

Memory & Complexity

  • Memory: O(n + m)
  • Iterate neighbors: O(deg(u))
  • Add edge: O(1)

JavaScript Examples

Unweighted

const adj = Array.from({ length: n }, () => []);

adj[u].push(v);    // directed
adj[v].push(u);    // undirected

Weighted

const adj = Array.from({ length: n }, () => []);

adj[u].push({ to: v, weight: w });
adj[v].push({ to: u, weight: w }); // if undirected

Pitfalls

  • hasEdge(u,v) costs O(deg(u))
  • No built-in capacity control like Java/C++

5. Edge List - short note 🔗

Structure:

const edges = [];
edges.push({ u, v });         // unweighted
edges.push({ u, v, w });      // weighted

Use-cases:

  • Kruskal’s MST
  • Bellman-Ford
  • Sorting edges

Memory: O(m) Neighbor queries: O(m)

6. Weighted graphs - storing weights 🪙

  • Adjacency List → best for Dijkstra
  • Adjacency Matrix → store weight or Infinity
  • Edge List → store {u,v,w}

⚠ Important: JavaScript uses Number (floating-point). For very large sums, consider careful overflow handling. For competitive programming scale, Number is usually fine.

7. Typical operations & cost table 📊

Operation Adjacency List Adjacency Matrix Edge List
Memory O(n + m) O(n²) O(m)
Iterate neighbors O(deg(u)) O(n) O(m)
hasEdge(u,v) O(deg(u)) O(1) O(m)
Add edge O(1) O(1) O(1)
Remove edge O(deg(u)) O(1) O(m)

8. Conversion helpers 🔁

Matrix → List

function matToList(mat) {
    const n = mat.length;
    const adj = Array.from({ length: n }, () => []);

    for (let u = 0; u < n; u++) {
        for (let v = 0; v < n; v++) {
            if (mat[u][v]) adj[u].push(v);
        }
    }
    return adj;
}

List → Matrix

function listToMat(adj) {
    const n = adj.length;
    const mat = Array.from({ length: n }, () => Array(n).fill(false));

    for (let u = 0; u < n; u++) {
        for (const v of adj[u]) {
            mat[u][v] = true;
        }
    }
    return mat;
}

9. Test cases ✅

A. Small unweighted

  • n = 4
  • edges: (0,1), (1,2), (2,3)

Check:

adj[1] // should contain 0 and 2
mat[0][1] === true
mat[3][0] === false

B. Weighted

  • edges: (0,1,5), (1,2,2)
  • Dijkstra from 0 → dist[2] = 7

10. Full single-file JavaScript reference 🧩

// graph_representations.js

const INF = Infinity;

// - Adjacency Matrix (Unweighted) -
function makeAdjMatrixUnweighted(n) {
    return Array.from({ length: n }, () => Array(n).fill(false));
}

function addEdgeMatUnweighted(mat, u, v, undirected = true) {
    mat[u][v] = true;
    if (undirected) mat[v][u] = true;
}

// - Adjacency Matrix (Weighted) -
function makeAdjMatrixWeighted(n) {
    const mat = Array.from({ length: n }, () => Array(n).fill(INF));
    for (let i = 0; i < n; i++) mat[i][i] = 0;
    return mat;
}

function addEdgeMatWeighted(mat, u, v, w, undirected = true) {
    mat[u][v] = w;
    if (undirected) mat[v][u] = w;
}

// - Adjacency List (Unweighted) -
function makeAdjListUnweighted(n) {
    return Array.from({ length: n }, () => []);
}

function addEdgeListUnweighted(adj, u, v, undirected = true) {
    adj[u].push(v);
    if (undirected) adj[v].push(u);
}

// - Adjacency List (Weighted) -
function makeAdjListWeighted(n) {
    return Array.from({ length: n }, () => []);
}

function addEdgeListWeighted(adj, u, v, w, undirected = true) {
    adj[u].push({ to: v, weight: w });
    if (undirected) adj[v].push({ to: u, weight: w });
}

// - Edge List -
function makeEdgeList() {
    return [];
}

function addEdgeEdgeList(edges, u, v, w) {
    edges.push({ u, v, w });
}

// - Dijkstra -
function dijkstra(src, adj) {
    const n = adj.length;
    const dist = Array(n).fill(INF);
    dist[src] = 0;

    const pq = [];
    pq.push({ node: src, dist: 0 });

    while (pq.length) {
        pq.sort((a, b) => a.dist - b.dist);
        const { node: u, dist: d } = pq.shift();

        if (d !== dist[u]) continue;

        for (const { to: v, weight: w } of adj[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({ node: v, dist: dist[v] });
            }
        }
    }

    return dist;
}

// - Demo -
function demo() {
    console.log("=== Graph Demo ===");

    const adj = makeAdjListWeighted(3);
    addEdgeListWeighted(adj, 0, 1, 5);
    addEdgeListWeighted(adj, 1, 2, 2);

    const dist = dijkstra(0, adj);
    console.log("Dijkstra dist 0->2:", dist[2], "(expect 7)");
}

demo();

11. Complexity recap 🔍

  • Adjacency matrix → O(n²) memory, O(1) edge checks
  • Adjacency list → O(n + m) memory, fast neighbor iteration
  • Edge list → O(m) memory, good for sorting edges

If m ≪ n², adjacency list almost always wins.

12. Tips & common pitfalls 🛠️

  • For small dense graphs → matrix works well
  • For large graphs → always use adjacency list
  • Use Infinity for “no edge” in weighted matrix
  • Avoid frequent Array.sort() in Dijkstra (use a proper min-heap for production)
  • For fast hasEdge(u,v) in sparse graphs → use Set:
const adj = Array.from({ length: n }, () => new Set());
adj[u].add(v);

13. Variations & extensions ✨

  • Use Map for weighted adjacency:
const adj = Array.from({ length: n }, () => new Map());
adj[u].set(v, weight);
  • CSR-like structure for performance-heavy workloads
  • Bitsets using typed arrays
  • Dynamic graph structures

14. FAQs ❓

Q: Which to memorize for interviews? A: Adjacency list.

Q: When use matrix? A: Small dense graphs or heavy edge-existence queries.

Q: Weighted Dijkstra best structure? A: Adjacency list.

Q: Large n (10⁵)? A: Matrix impossible. Use adjacency list.

15. Final checklist ✅

  • Graph dense or sparse?
  • Need fast hasEdge?
  • Weighted or unweighted?
  • Could numbers overflow?
  • Need fast priority queue?