06 — Graph Advanced

Minimum Spanning Tree (MST)

Connects all vertices with minimum total edge weight, no cycles.

Kruskal's Algorithm (Edge-based)

Sort edges by weight, add if no cycle (Union-Find).

function kruskal(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]); // Sort by weight
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);
  
  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }
  
  function union(x: number, y: number): boolean {
    const px = find(x), py = find(y);
    if (px === py) return false;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
    return true;
  }
  
  let cost = 0, edgeCount = 0;
  for (const [u, v, w] of edges) {
    if (union(u, v)) {
      cost += w;
      if (++edgeCount === n - 1) break;
    }
  }
  return cost;
}

Prim's Algorithm (Vertex-based)

Grow MST from a starting vertex using min-heap.

function prim(adj: [number, number][][], n: number): number {
  const visited = new Array(n).fill(false);
  const pq: [number, number][] = [[0, 0]]; // [weight, node]
  let cost = 0, count = 0;
  
  while (pq.length && count < n) {
    pq.sort((a, b) => a[0] - b[0]);
    const [w, u] = pq.shift()!;
    if (visited[u]) continue;
    visited[u] = true;
    cost += w;
    count++;
    
    for (const [v, weight] of adj[u]) {
      if (!visited[v]) pq.push([weight, v]);
    }
  }
  return cost;
}

---

Bridges (Cut Edges)

Edge whose removal disconnects the graph.

function findBridges(adj: number[][], n: number): [number, number][] {
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const bridges: [number, number][] = [];
  let timer = 0;
  
  function dfs(u: number, parent: number) {
    disc[u] = low[u] = timer++;
    
    for (const v of adj[u]) {
      if (v === parent) continue;
      if (disc[v] === -1) {
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) {
          bridges.push([u, v]); // Bridge found
        }
      } else {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }
  
  for (let i = 0; i < n; i++) {
    if (disc[i] === -1) dfs(i, -1);
  }
  return bridges;
}

---

Articulation Points (Cut Vertices)

Vertex whose removal disconnects the graph.

function articulationPoints(adj: number[][], n: number): number[] {
  const disc = new Array(n).fill(-1);
  const low = new Array(n).fill(-1);
  const isAP = new Array(n).fill(false);
  let timer = 0;
  
  function dfs(u: number, parent: number) {
    disc[u] = low[u] = timer++;
    let children = 0;
    
    for (const v of adj[u]) {
      if (disc[v] === -1) {
        children++;
        dfs(v, u);
        low[u] = Math.min(low[u], low[v]);
        
        if (parent === -1 && children > 1) isAP[u] = true;       // Root with 2+ children
        if (parent !== -1 && low[v] >= disc[u]) isAP[u] = true;  // Non-root
      } else if (v !== parent) {
        low[u] = Math.min(low[u], disc[v]);
      }
    }
  }
  
  for (let i = 0; i < n; i++) {
    if (disc[i] === -1) dfs(i, -1);
  }
  return Array.from({ length: n }, (_, i) => i).filter(i => isAP[i]);
}

---

Strongly Connected Components (Kosaraju's)

Directed graph: maximal groups where every vertex is reachable from every other.

function scc(adj: number[][], n: number): number[][] {
  const visited = new Array(n).fill(false);
  const order: number[] = [];
  
  // Pass 1: DFS, record finish order
  function dfs1(u: number) {
    visited[u] = true;
    for (const v of adj[u]) if (!visited[v]) dfs1(v);
    order.push(u);
  }
  
  for (let i = 0; i < n; i++) if (!visited[i]) dfs1(i);
  
  // Build reverse graph
  const radj: number[][] = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) for (const v of adj[u]) radj[v].push(u);
  
  // Pass 2: DFS on reverse graph in reverse finish order
  visited.fill(false);
  const components: number[][] = [];
  
  function dfs2(u: number, comp: number[]) {
    visited[u] = true;
    comp.push(u);
    for (const v of radj[u]) if (!visited[v]) dfs2(v, comp);
  }
  
  for (let i = n - 1; i >= 0; i--) {
    const u = order[i];
    if (!visited[u]) {
      const comp: number[] = [];
      dfs2(u, comp);
      components.push(comp);
    }
  }
  return components;
}

---

Key Takeaways

• MST: Kruskal (sort edges + Union-Find) for sparse; Prim (min-heap) for dense
• Bridges/Articulation Points: Use disc[] and low[] arrays in DFS
• Bridge: low[v] > disc[u]; Articulation Point: low[v] >= disc[u]
• SCC (Kosaraju's): two-pass DFS — first on original, second on reversed graph
• These are hard interview/competitive programming topics — know when to apply them