跳到主要内容

最小生成树

最小生成树（Minimum Spanning Tree, MST）是图中包含所有顶点的权值之和最小的子图，且无环（必须含有 V-1 条边）。

核心算法​

图的 MST 取决于图是否连通。

1. Prim 算法 (基于顶点)​

从一个点出发，每次选择与当前生成树最近的未加入顶点，将其并入。

  • 适用场景：适合 稠密图（边多）。
  • 时间复杂度：
    • 朴素实现：O(V²)
    • 优先队列优化：O(E log V)
public int prim(int n) {
    int[] lowCost = new int[n];        // 节点到生成树的最小代价
    boolean[] inTree = new boolean[n]; // 节点是否在生成树中
    Arrays.fill(lowCost, Integer.MAX_VALUE);
    lowCost[0] = 0;
    int total = 0;
    for (int i = 0; i < n; i++) {
        int u = findMin(lowCost, inTree);
        if (u == -1) return -1;  // 图不连通
        inTree[u] = true;
        total += lowCost[u];
        // 更新与 u 相邻的所有节点的 lowCost
        updateNeighbor(u, lowCost, inTree);
    }
    return total;
}

2. Kruskal 算法 (基于边)​

将所有边按权值排序，依次加入生成树，前提是所加边不形成环。

  • 核心工具：并查集 (Union-Find) 用于快速检测环。
  • 适用场景：适合 稀疏图（边少）。
  • 时间复杂度：O(E log E) 时间。
public int kruskal(int n, List<Edge> edges) {
    Collections.sort(edges, (a, b) -> a.weight - b.weight);
    UnionFind uf = new UnionFind(n);
    int total = 0, count = 0;
    for (Edge e : edges) {
        if (uf.union(e.u, e.v)) {
            total += e.weight;
            count++;
            if (count == n - 1) break;
        }
    }
    return count == n - 1 ? total : -1;
}

并查集 Union-Find (额外补充)​

并查集用于处理不相交集合的合并与查找。

优化手段​

  1. 路径压缩 (Path Compression)：使 find 准 O(1)。
  2. 按秩合并 (Union by Rank/Size)：保持树平衡。
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

练习​

  1. LeetCode 1584：连接所有点的最小费用 (Prim/Kruskal)
  2. LeetCode 547：省份数量 (并查集/DFS)
  3. LeetCode 684：冗余连接 (检测无向图环)
  4. 理解并实现并查集的路径压缩优化。