Graphs

Adjacency List: Each vertex stores a list of its neighbors. Space-efficient for sparse graphs.

Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there is an edge from i to j. Fast edge lookup.

// Adjacency List:
const adjList = { 0: [1, 2], 1: [0, 3], 2: [0], 3: [1] };

// Adjacency Matrix:
const adjMatrix = [
    [0, 1, 1, 0],  // 0 connects to 1, 2
    [1, 0, 0, 1],  // 1 connects to 0, 3
    [1, 0, 0, 0],  // 2 connects to 0
    [0, 1, 0, 0]   // 3 connects to 1
];

• List — Space: O(V + E), Edge lookup: O(degree)
• Matrix — Space: O(V²), Edge lookup: O(1)

Use list for sparse graphs, matrix for dense graphs or when you need fast edge checks.

BFS explores a graph level by level using a queue. It finds the shortest path in unweighted graphs.

function bfs(graph, start) {
    const visited = new Set([start]);
    const queue = [start];
    const order = [];

    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const neighbor of (graph[node] || [])) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return order;
}
// graph = { A:['B','C'], B:['D'], C:['D','E'], D:[], E:[] }
// bfs(graph, 'A') => ['A','B','C','D','E']

Time: O(V + E)  |  Space: O(V)

DFS explores as deep as possible along each branch before backtracking. It uses a stack (or recursion).

// Recursive DFS
function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    const result = [node];
    for (const neighbor of (graph[node] || [])) {
        if (!visited.has(neighbor)) {
            result.push(...dfs(graph, neighbor, visited));
        }
    }
    return result;
}

// Iterative DFS
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    const result = [];
    while (stack.length) {
        const node = stack.pop();
        if (visited.has(node)) continue;
        visited.add(node);
        result.push(node);
        for (const neighbor of (graph[node] || [])) {
            stack.push(neighbor);
        }
    }
    return result;
}

Time: O(V + E)  |  Space: O(V). DFS is used for cycle detection, topological sorting, and path finding.

Use DFS: if you visit a neighbor that is already visited and is not the parent of the current node, a cycle exists.

function hasCycleUndirected(graph, numNodes) {
    const visited = new Set();

    function dfs(node, parent) {
        visited.add(node);
        for (const neighbor of (graph[node] || [])) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor, node)) return true;
            } else if (neighbor !== parent) {
                return true; // cycle found
            }
        }
        return false;
    }

    // Check all components
    for (let i = 0; i < numNodes; i++) {
        if (!visited.has(i)) {
            if (dfs(i, -1)) return true;
        }
    }
    return false;
}

Time: O(V + E)  |  Space: O(V). Alternatively, use Union-Find for cycle detection.

Use DFS with three states: unvisited, in-progress (on current path), and completed. If you revisit an in-progress node, there is a cycle.

function hasCycleDirected(graph, numNodes) {
    const WHITE = 0, GRAY = 1, BLACK = 2;
    const color = new Array(numNodes).fill(WHITE);

    function dfs(node) {
        color[node] = GRAY; // in-progress
        for (const neighbor of (graph[node] || [])) {
            if (color[neighbor] === GRAY) return true; // back edge = cycle
            if (color[neighbor] === WHITE && dfs(neighbor)) return true;
        }
        color[node] = BLACK; // completed
        return false;
    }

    for (let i = 0; i < numNodes; i++) {
        if (color[i] === WHITE && dfs(i)) return true;
    }
    return false;
}

Time: O(V + E)  |  Space: O(V)

Topological sort orders vertices in a DAG (Directed Acyclic Graph) so that for every edge u → v, u appears before v. Used for task scheduling and dependency resolution.

function topologicalSort(graph, numNodes) {
    const inDegree = new Array(numNodes).fill(0);
    for (const node in graph) {
        for (const neighbor of graph[node]) inDegree[neighbor]++;
    }

    const queue = [];
    for (let i = 0; i < numNodes; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }

    const order = [];
    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const neighbor of (graph[node] || [])) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) queue.push(neighbor);
        }
    }
    return order.length === numNodes ? order : []; // empty if cycle
}

Time: O(V + E)  |  Space: O(V). This is Kahn's algorithm (BFS-based).

Dijkstra's algorithm finds the shortest path from a source to all vertices in a weighted graph with non-negative edges. It uses a priority queue (min-heap).

function dijkstra(graph, start) {
    const dist = {};
    for (const node in graph) dist[node] = Infinity;
    dist[start] = 0;
    const pq = [[0, start]]; // [distance, node]

    while (pq.length) {
        pq.sort((a, b) => a[0] - b[0]); // min-heap simulation
        const [d, u] = pq.shift();
        if (d > dist[u]) continue;

        for (const [v, weight] of graph[u]) {
            const newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push([newDist, v]);
            }
        }
    }
    return dist;
}
// graph = { A: [['B',1],['C',4]], B: [['C',2]], C: [] }
// dijkstra(graph, 'A') => { A: 0, B: 1, C: 3 }

Time: O((V + E) log V) with a proper min-heap  |  Space: O(V)

Use DFS or BFS from each unvisited node. Each traversal discovers one connected component.

function connectedComponents(graph, numNodes) {
    const visited = new Set();
    const components = [];

    function dfs(node, component) {
        visited.add(node);
        component.push(node);
        for (const neighbor of (graph[node] || [])) {
            if (!visited.has(neighbor)) dfs(neighbor, component);
        }
    }

    for (let i = 0; i < numNodes; i++) {
        if (!visited.has(i)) {
            const component = [];
            dfs(i, component);
            components.push(component);
        }
    }
    return components;
}
// graph = { 0:[1], 1:[0], 2:[3], 3:[2], 4:[] }
// connectedComponents(graph, 5)
// => [[0,1], [2,3], [4]]

Time: O(V + E)  |  Space: O(V)

A tree is a special type of graph with specific constraints:

• Tree: Connected, acyclic, undirected graph with exactly V - 1 edges. Has a root and hierarchical structure.
• Graph: General structure with no restrictions on cycles, connectivity, or edge count.

Every tree is a graph, but not every graph is a tree.

Iterate over all nodes. For each unvisited node, launch a BFS/DFS to visit all reachable nodes, marking them visited. Each launch = one component.

function connectedComponents(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    const visited = new Array(n).fill(false);
    let components = 0;
    function dfs(node) {
        visited[node] = true;
        for (const nb of adj[node]) if (!visited[nb]) dfs(nb);
    }
    for (let i = 0; i < n; i++) {
        if (!visited[i]) { components++; dfs(i); }
    }
    return components;
}
// Input: n=5, edges=[[0,1],[1,2],[3,4]]  => Output: 2
// Input: n=5, edges=[[0,1],[0,2],[3,4]]  => Output: 2  ({0,1,2} and {3,4})

Time: O(V + E)  |  Space: O(V)

Use Kahn's algorithm (BFS): compute in-degrees, start with all zero-in-degree nodes, process and reduce neighbors' in-degrees. An alternative is DFS post-order.

function topologicalSort(numCourses, prerequisites) {
    const adj = Array.from({length: numCourses}, () => []);
    const inDegree = new Array(numCourses).fill(0);
    for (const [a, b] of prerequisites) { adj[b].push(a); inDegree[a]++; }
    const queue = [];
    for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
    const order = [];
    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const nb of adj[node]) {
            if (--inDegree[nb] === 0) queue.push(nb);
        }
    }
    return order.length === numCourses ? order : []; // empty = cycle
}
// Input: n=4, edges=[[1,0],[2,0],[3,1],[3,2]]  => Output: [0,1,2,3] or [0,2,1,3]

Time: O(V + E)  |  Space: O(V + E)

Use DFS with three states: unvisited (0), in-progress/gray (1), done/black (2). A back edge to a gray node indicates a cycle.

function hasCycleDirected(n, edges) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    const state = new Array(n).fill(0); // 0=unvisited,1=gray,2=black
    function dfs(node) {
        state[node] = 1;
        for (const nb of adj[node]) {
            if (state[nb] === 1) return true;  // back edge = cycle
            if (state[nb] === 0 && dfs(nb)) return true;
        }
        state[node] = 2;
        return false;
    }
    for (let i = 0; i < n; i++) if (state[i] === 0 && dfs(i)) return true;
    return false;
}
// Input: n=4, edges=[[0,1],[1,2],[2,3],[3,1]]  => Output: true  (cycle 1-2-3)
// Input: n=4, edges=[[0,1],[0,2],[1,3]]         => Output: false

Time: O(V + E)  |  Space: O(V)

Bellman-Ford handles negative weights (unlike Dijkstra). Relax all edges V-1 times. A Vth relaxation means a negative cycle exists.

function bellmanFord(n, edges, src) {
    // edges: [[u, v, weight], ...]
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    for (let i = 0; i < n - 1; i++) {
        for (const [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    // Check for negative cycles
    for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
            return null; // negative cycle detected
        }
    }
    return dist;
}
// Input: n=5, src=0, edges=[[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]]
// Output: [0,-1,2,-2,1]

Time: O(V × E)  |  Space: O(V)

Sort edges by weight. Use Union-Find: greedily add the cheapest edge that doesn't form a cycle. Stop when V-1 edges are added.

function kruskal(n, edges) {
    edges.sort((a, b) => a[2] - b[2]); // sort by weight
    const parent = Array.from({length: n}, (_, i) => i);
    function find(x) { return parent[x] === x ? x : (parent[x] = find(parent[x])); }
    function union(x, y) {
        const px = find(x), py = find(y);
        if (px === py) return false; // would form cycle
        parent[px] = py;
        return true;
    }
    let mstCost = 0, edgesUsed = 0;
    for (const [u, v, w] of edges) {
        if (union(u, v)) { mstCost += w; edgesUsed++; }
        if (edgesUsed === n - 1) break;
    }
    return edgesUsed === n - 1 ? mstCost : -1; // -1 if not fully connected
}
// 4 nodes: edges=[[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,3]]
// MST: edges (0,1),(1,2),(2,3) cost = 1+2+3 = 6

Time: O(E log E) for sorting  |  Space: O(V)

Use DFS/BFS with a hash map from original node → cloned node. For each unvisited node, create a clone and recursively clone its neighbors.

function cloneGraph(node) {
    if (!node) return null;
    const visited = new Map();
    function dfs(curr) {
        if (visited.has(curr)) return visited.get(curr);
        const clone = { val: curr.val, neighbors: [] };
        visited.set(curr, clone);
        for (const nb of curr.neighbors) {
            clone.neighbors.push(dfs(nb));
        }
        return clone;
    }
    return dfs(node);
}
// Input: node 1 with neighbors [2,4], node 2 with [1,3], etc.
// Output: deep copy of the entire graph

Time: O(V + E)  |  Space: O(V)

Use Tarjan's bridge-finding algorithm. Track discovery time and low values. An edge (u,v) is a bridge if low[v] > disc[u] (v cannot reach u or earlier without going through u-v).

function criticalConnections(n, connections) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of connections) { adj[u].push(v); adj[v].push(u); }
    const disc = new Array(n).fill(-1);
    const low  = new Array(n).fill(-1);
    const bridges = [];
    let timer = 0;
    function dfs(node, parent) {
        disc[node] = low[node] = timer++;
        for (const nb of adj[node]) {
            if (disc[nb] === -1) {
                dfs(nb, node);
                low[node] = Math.min(low[node], low[nb]);
                if (low[nb] > disc[node]) bridges.push([node, nb]);
            } else if (nb !== parent) {
                low[node] = Math.min(low[node], disc[nb]);
            }
        }
    }
    for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
    return bridges;
}
// Input: n=4, connections=[[0,1],[1,2],[2,0],[1,3]]  => Output: [[1,3]]

Time: O(V + E)  |  Space: O(V)

Union-Find efficiently tracks which elements belong to the same set. Two key operations: find (with path compression) and union (with rank).

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] = py;
        else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
        else { this.parent[py] = px; this.rank[px]++; }
        return true;
    }
}
// UF(5): union(0,1), union(1,2) => find(0)===find(2) is true
// union(3,4): find(0)!==find(3) (different components)

Time: O(α(n)) per operation (inverse Ackermann, nearly O(1))  |  Space: O(n)

Treat as connected components. Use DFS or Union-Find: merge connected cities. Count distinct roots at the end.

function findCircleNum(isConnected) {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);
    function dfs(i) {
        visited[i] = true;
        for (let j = 0; j < n; j++) {
            if (isConnected[i][j] === 1 && !visited[j]) dfs(j);
        }
    }
    let provinces = 0;
    for (let i = 0; i < n; i++) {
        if (!visited[i]) { provinces++; dfs(i); }
    }
    return provinces;
}
// Input: [[1,1,0],[1,1,0],[0,0,1]]  => Output: 2  ({0,1} and {2})
// Input: [[1,0,0],[0,1,0],[0,0,1]]  => Output: 3  (all separate)

Time: O(n²)  |  Space: O(n)

Two-pass DFS. Pass 1: run DFS on original graph, push nodes to stack in finish order. Pass 2: process nodes from stack on the transposed graph.

function kosarajuSCC(n, edges) {
    const adj  = Array.from({length: n}, () => []);
    const radj = Array.from({length: n}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); radj[v].push(u); }
    const visited = new Array(n).fill(false);
    const stack = [];
    function dfs1(u) {
        visited[u] = true;
        for (const v of adj[u]) if (!visited[v]) dfs1(v);
        stack.push(u);
    }
    for (let i = 0; i < n; i++) if (!visited[i]) dfs1(i);
    visited.fill(false);
    let sccCount = 0;
    function dfs2(u) {
        visited[u] = true;
        for (const v of radj[u]) if (!visited[v]) dfs2(v);
    }
    while (stack.length) {
        const node = stack.pop();
        if (!visited[node]) { sccCount++; dfs2(node); }
    }
    return sccCount;
}
// Directed graph with 4 SCCs: each strongly connected cluster counts as 1

Time: O(V + E)  |  Space: O(V + E)

Each word is a node; edges exist between words differing by one letter. Use BFS for the shortest path from beginWord to endWord.

function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;
    const queue = [[beginWord, 1]]; // [word, steps]
    const visited = new Set([beginWord]);
    while (queue.length) {
        const [word, steps] = queue.shift();
        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) { // a-z
                const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i+1);
                if (next === endWord) return steps + 1;
                if (wordSet.has(next) && !visited.has(next)) {
                    visited.add(next); queue.push([next, steps + 1]);
                }
            }
        }
    }
    return 0;
}
// Input: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]
// Output: 5  (hit->hot->dot->dog->cog)

Time: O(M² × N) where M=word length, N=wordList size  |  Space: O(M² × N)