最小生成樹 — Kruskal 與 Prim 演算法完整比較與實作 | 資料結構與演算法

class UnionFind {
  private parent: number[];
  private rank: number[];

  constructor(n: number) {
    // 初始化：每個節點的父節點是自己
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x: number): number {
    // 路徑壓縮：將沿途所有節點直接指向根節點
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const rx = this.find(x);
    const ry = this.find(y);
    if (rx === ry) return false; // 已連通，加入此邊會成環
    // 按秩合併：秩小的樹接在秩大的樹下
    if (this.rank[rx] < this.rank[ry]) {
      this.parent[rx] = ry;
    } else if (this.rank[rx] > this.rank[ry]) {
      this.parent[ry] = rx;
    } else {
      this.parent[ry] = rx;
      this.rank[rx]++;
    }
    return true; // 成功合併
  }
}

class MinHeap<T> {
  private heap: T[] = [];

  constructor(private compare: (a: T, b: T) => number) {}

  push(val: T): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  get size(): number {
    return this.heap.length;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.heap[i], this.heap[parent]) < 0) {
        [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
        i = parent;
      } else {
        break;
      }
    }
  }

  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.compare(this.heap[l], this.heap[smallest]) < 0) smallest = l;
      if (r < n && this.compare(this.heap[r], this.heap[smallest]) < 0) smallest = r;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

// 輸入：n 個頂點（0-indexed），edges = [u, v, weight][]
// 輸出：MST 的邊列表；若圖不連通，返回能覆蓋的最小生成森林

function kruskal(
  n: number,
  edges: [number, number, number][]
): [number, number, number][] {
  // Step 1：按邊權升序排列
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(n);
  const mst: [number, number, number][] = [];

  for (const [u, v, w] of edges) {
    // Step 2：嘗試合併；若兩端已連通則跳過
    if (uf.union(u, v)) {
      mst.push([u, v, w]);
      // Step 3：MST 恰有 V-1 條邊即完成
      if (mst.length === n - 1) break;
    }
  }

  return mst;
}

// 計算 MST 總權重
function kruskalMSTWeight(n: number, edges: [number, number, number][]): number {
  const mstEdges = kruskal(n, [...edges]); // 複製避免修改原陣列
  return mstEdges.reduce((sum, [, , w]) => sum + w, 0);
}

// 範例
const n = 6;
const edges: [number, number, number][] = [
  [0, 1, 4], [0, 2, 3], [1, 2, 2], [1, 3, 6],
  [2, 3, 5], [2, 4, 4], [2, 5, 1], [3, 5, 4], [4, 5, 1],
];
console.log(kruskalMSTWeight(n, edges)); // 輸出：11

// 輸入：n 個頂點，adj = 鄰接表，adj[u] = [[v, weight], ...]
// 輸出：MST 總權重；若圖不連通返回 -1

function prim(n: number, adj: [number, number][][]): number {
  const visited = new Uint8Array(n); // 0=未加入，1=已加入 MST
  // MinHeap 儲存 [weight, toNode]
  const heap = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  let totalWeight = 0;
  let edgeCount = 0;

  // 從頂點 0 出發，將 0 的所有鄰邊加入 Heap
  visited[0] = 1;
  for (const [neighbor, weight] of adj[0]) {
    heap.push([weight, neighbor]);
  }

  while (heap.size > 0 && edgeCount < n - 1) {
    const item = heap.pop();
    if (!item) break;
    const [weight, u] = item;

    if (visited[u]) continue; // Lazy Deletion：跳過已在 MST 中的頂點

    // 將 u 加入 MST
    visited[u] = 1;
    totalWeight += weight;
    edgeCount++;

    // 將 u 的所有未加入 MST 的鄰邊推入 Heap
    for (const [neighbor, w] of adj[u]) {
      if (!visited[neighbor]) {
        heap.push([w, neighbor]);
      }
    }
  }

  // edgeCount < n-1 代表圖不連通
  return edgeCount === n - 1 ? totalWeight : -1;
}

// 建圖輔助函式（無向圖）
function buildAdjList(
  n: number,
  edges: [number, number, number][]
): [number, number][][] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);
    adj[v].push([u, w]); // 無向圖：雙向加邊
  }
  return adj;
}

// 範例
const adj = buildAdjList(n, edges);
console.log(prim(n, adj)); // 輸出：11

#include <bits/stdc++.h>
using namespace std;

// ===== Union-Find（供 Kruskal 使用）=====
struct UnionFind {
    vector<int> parent, rank_;
    explicit UnionFind(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路徑壓縮
        return parent[x];
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        return true;
    }
};

// ===== Kruskal：O(E log E) =====
// edges: vector<tuple<weight, u, v>>
long long kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end()); // 按 weight 升序（tuple 預設按第一個元素）

    UnionFind uf(n);
    long long totalWeight = 0;
    int edgeCount = 0;

    for (auto& [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            totalWeight += w;
            if (++edgeCount == n - 1) break; // MST 完成
        }
    }
    return edgeCount == n - 1 ? totalWeight : -1; // -1 表示圖不連通
}

// ===== Prim：O((V+E) log V)，priority_queue 版 =====
long long prim(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> visited(n, false);
    // Min-Heap：{weight, node}
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;

    pq.push({0, 0}); // 從節點 0 出發，初始虛擬邊權 = 0
    long long totalWeight = 0;
    int edgeCount = 0;

    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();

        if (visited[u]) continue; // Lazy Deletion
        visited[u] = true;
        totalWeight += w;
        if (u != 0) edgeCount++; // 起點虛擬邊不計入邊數

        for (auto& [v, weight] : adj[u]) {
            if (!visited[v]) pq.push({weight, v});
        }
    }
    return edgeCount == n - 1 ? totalWeight : -1;
}

int main() {
    int n = 6;
    // Kruskal 輸入：{weight, u, v}
    vector<tuple<int,int,int>> edges = {
        {4,0,1},{3,0,2},{2,1,2},{6,1,3},
        {5,2,3},{4,2,4},{1,2,5},{4,3,5},{1,4,5}
    };
    cout << kruskal(n, edges) << "\n"; // 11

    // Prim 輸入：鄰接表
    vector<vector<pair<int,int>>> adj(n);
    for (auto& [w, u, v] : edges) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cout << prim(n, adj) << "\n"; // 11
    return 0;
}

// 錯誤寫法：沒有檢查 visited
while (heap.size > 0) {
  const [weight, u] = heap.pop()!;
  visited[u] = 1;      // 若 u 已加入，這裡會重複計算！
  totalWeight += weight;
}

// 正確寫法：
const [weight, u] = heap.pop()!;
if (visited[u]) continue; // 必須有這行

function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  if (n === 1) return 0;

  // 稠密圖優化版 Prim：不使用 MinHeap，改用 minDist 陣列線性掃描
  // 時間 O(n²)，空間 O(n)，比 MinHeap 版 O(n² log n) 更優（稠密完全圖）
  const minDist = new Array(n).fill(Infinity); // minDist[i] = 點 i 到 MST 的最小距離
  const inMST = new Uint8Array(n);
  minDist[0] = 0; // 從點 0 出發
  let totalCost = 0;

  for (let iter = 0; iter < n; iter++) {
    // 找到距離 MST 最近的未加入點
    let u = -1;
    for (let i = 0; i < n; i++) {
      if (!inMST[i] && (u === -1 || minDist[i] < minDist[u])) {
        u = i;
      }
    }

    inMST[u] = 1;
    totalCost += minDist[u];

    // 更新所有未加入點到 MST 的最小距離
    for (let v = 0; v < n; v++) {
      if (!inMST[v]) {
        const dist = Math.abs(points[u][0] - points[v][0]) +
                     Math.abs(points[u][1] - points[v][1]);
        if (dist < minDist[v]) {
          minDist[v] = dist;
        }
      }
    }
  }

  return totalCost;
  // 時間：O(n²)    空間：O(n)
}

// 測試
console.log(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])); // 輸出：20
console.log(minCostConnectPoints([[3,12],[-2,5],[-4,1]]));           // 輸出：18

function findCriticalAndPseudoCriticalEdges(
  n: number,
  edges: number[][]
): number[][] {
  // 記錄原始邊索引（排序後需還原）
  const indexedEdges = edges.map((e, i) => [...e, i]);
  indexedEdges.sort((a, b) => a[2] - b[2]); // 按權重排序

  // Kruskal 輔助函式
  // skipIdx：強制排除的邊索引（-1 表示不排除）
  // forceIdx：強制包含的邊索引（-1 表示不強制）
  // 回傳 MST 重量，圖不連通回傳 Infinity
  function kruskalWith(skipIdx: number, forceIdx: number): number {
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = new Array(n).fill(0);
    let totalWeight = 0;
    let edgeCount = 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 rx = find(x), ry = find(y);
      if (rx === ry) return false;
      if (rank[rx] < rank[ry]) parent[rx] = ry;
      else if (rank[rx] > rank[ry]) parent[ry] = rx;
      else { parent[ry] = rx; rank[rx]++; }
      return true;
    }

    // 先強制加入 forceIdx 的邊
    if (forceIdx !== -1) {
      const [u, v, w] = indexedEdges[forceIdx];
      union(u, v);
      totalWeight += w;
      edgeCount++;
    }

    for (let i = 0; i < indexedEdges.length; i++) {
      if (i === skipIdx) continue;
      const [u, v, w] = indexedEdges[i];
      if (union(u, v)) {
        totalWeight += w;
        edgeCount++;
      }
    }

    return edgeCount === n - 1 ? totalWeight : Infinity;
  }

  const baseMST = kruskalWith(-1, -1);
  const critical: number[] = [];
  const pseudoCritical: number[] = [];

  for (let i = 0; i < indexedEdges.length; i++) {
    const originalIdx = indexedEdges[i][3]; // 還原原始邊索引

    if (kruskalWith(i, -1) > baseMST) {
      // 強制排除後 MST 重量增加 → 關鍵邊
      critical.push(originalIdx);
    } else if (kruskalWith(-1, i) === baseMST) {
      // 強制包含後 MST 重量不變 → 偽關鍵邊
      pseudoCritical.push(originalIdx);
    }
  }

  return [critical, pseudoCritical];
  // 時間：O(E² × α(V))    空間：O(V + E)
}

// 測試
console.log(findCriticalAndPseudoCriticalEdges(5, [
  [0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]
]));
// 輸出：[[0,1], [2,3,4,5]]

console.log(findCriticalAndPseudoCriticalEdges(4, [
  [0,1,1],[1,2,1],[2,3,1],[0,3,1]
]));
// 輸出：[[], [0,1,2,3]]