• Overview and Definitions
• Kruskal's Algorithm (DSU)
• Prim's Algorithm (Heap)
• Cut/ Cycle Properties and Proof Sketches
• Pitfalls and Notes
• Exercises

• MST: A subset of edges connecting all vertices with minimum total weight (for connected, undirected, weighted graphs).
• Uniqueness: Unique if all edge weights are distinct; otherwise multiple MSTs may exist with same weight.
• Assumptions: Non-negative weights not required; graph must be connected for a spanning tree (otherwise spanning forest).

// edges: [{u, v, w}], n nodes (0..n-1)
function kruskal(n, edges) {
  edges = edges.slice().sort((a,b) => a.w - b.w);
  const parent = Array(n).fill(0).map((_,i) => i);
  const rank = Array(n).fill(0);
  function find(x){ return parent[x]===x? x : parent[x]=find(parent[x]); }
  function unite(a,b){ a=find(a); b=find(b); if(a===b) return false; if(rank[a] spanning forest
  return { edges: mst, weight: total };
}

• Complexity: O(m log m) for sorting + near-linear DSU.
• When good: sparse graphs; fast and simple with sorted edges.

// adj: Array of arrays of {to, w}; start from node 0 (or any)
function prim(adj, s = 0) {
  const n = adj.length; const used = Array(n).fill(false);
  const heap = [];
  const up = (i)=>{ while(i){ const p=(i-1)>>1; if(heap[p][0]<=heap[i][0]) break; [heap[p],heap[i]]=[heap[i],heap[p]]; i=p; } };
  const down=(i)=>{ for(;;){ let l=i*2+1,r=l+1,m=i; if(l{ heap.push(x); up(heap.length-1); };
  const pop=()=>{ const t=heap[0]; const last=heap.pop(); if(heap.length){ heap[0]=last; down(0);} return t; };
  used[s]=true; let total=0; const mstEdges=[];
  for (const e of adj[s]) push([e.w, s, e.to]);
  let picked=0;
  while (heap.length && picked < n-1) {
    const [w, u, v] = pop(); if (used[v]) continue;
    used[v]=true; total+=w; mstEdges.push({u, v, w}); picked++;
    for (const e of adj[v]) if (!used[e.to]) push([e.w, v, e.to]);
  }
  // If graph disconnected, picked < n-1 -> spanning forest for reachable nodes
  return { edges: mstEdges, weight: total };
}

• Complexity: O(m log n) with a binary heap and adjacency list.
• When good: dense-ish graphs or when starting from a vertex is convenient.

• Cut property: For any cut, the lightest edge crossing it is in some MST.
• Cycle property: For any cycle, the heaviest edge is not in any MST.
• Proof sketch: Exchange argument: swap edges to improve or maintain optimality.

• Edge weights can be negative; algorithms still valid.
• Disconnected graphs: result is a minimum spanning forest.
• For Prim, avoid pushing edges into heap for already-used nodes unless you filter on pop.

1. Implement DSU with path compression + union by rank and integrate into Kruskal.
2. Implement Prim with adjacency list and binary heap; compare vs. Kruskal on random graphs.
3. Prove the cut property formally using exchange arguments.