最小生成树

最小生成树(Minimum Spanning Tree, MST)是图论中的一个重要概念，在网络设计、电路布线等实际问题中有广泛应用。

基本概念

【定义】给定一个带权无向连通图G=(V,E)，图中每条边e都有一个权值w(e)。最小生成树是一个包含G中所有顶点的无环连通子图，且所有边的权值之和最小。

关键特性：

1. MST包含图G的所有顶点
2. MST是一棵树（无环连通图）
3. MST的边权之和在所有生成树中最小

Kruskal算法

【算法】Kruskal算法是一种贪心算法，基于边的选择策略：按照边权从小到大的顺序选择边，如果加入该边不会形成环，则将其加入生成树。

算法步骤

1. 将所有边按权值升序排序
2. 初始时，每个顶点构成一个独立的连通分量
3. 按排序后的顺序考察每条边(u,v)：
   • 如果u和v不在同一连通分量，则将该边加入生成树，并合并u和v所在的连通分量
   • 否则，丢弃该边
4. 重复步骤3，直到加入n-1条边（n为顶点数）或考察完所有边

代码实现

Kruskal算法通常使用并查集来判断两个顶点是否在同一连通分量：

struct Edge {
    int u, v, weight;

    Edge(int _u, int _v, int _w) : u(_u), v(_v), weight(_w) {}

    // 重载小于运算符，用于边的排序
    bool operator < (const Edge& other) const {
        return weight < other.weight;
    }
};

vector<Edge> edges; // 存储所有边
vector<Edge> mst;   // 存储最小生成树的边

// 并查集数据结构
int parent[MAXN];
int rank[MAXN];  // 用于按秩合并

// 初始化并查集
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;   // 每个节点的父节点初始为自己
        rank[i] = 0;     // 初始秩为0
    }
}

// 查找节点所在集合的代表（带路径压缩）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

// 合并两个集合（按秩合并）
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) return;

    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

// Kruskal算法实现
int kruskal(int n) {
    // 初始化并查集
    init(n);

    // 对所有边按权值排序
    sort(edges.begin(), edges.end());

    int totalWeight = 0;  // 最小生成树的总权值
    int edgeCount = 0;    // 已加入生成树的边数

    // 按权值从小到大遍历所有边
    for (const Edge& e : edges) {
        int rootU = find(e.u);
        int rootV = find(e.v);

        // 如果加入这条边不会形成环
        if (rootU != rootV) {
            mst.push_back(e);  // 将边加入MST
            totalWeight += e.weight;
            unionSets(rootU, rootV);  // 合并集合
            edgeCount++;

            // 如果已经有n-1条边，MST构建完成
            if (edgeCount == n - 1) {
                break;
            }
        }
    }

    // 检查是否形成了一个完整的生成树
    return (edgeCount == n - 1) ? totalWeight : -1;  // -1表示图不连通
}

时间复杂度分析

• 排序：O(E log E)
• 并查集操作：近似O(E)（使用路径压缩和按秩合并）
• 总时间复杂度：O(E log E) 或 O(E log V)，因为E最多为V²，所以log E = O(log V)

Prim算法

【算法】Prim算法也是一种贪心算法，但它基于顶点的选择策略：每次选择与已选顶点集合相邻的、权值最小的边所连接的顶点。

算法步骤

1. 选择任意一个顶点作为起点，加入已选顶点集合S
2. 初始化一个数组key，key[v]表示顶点v与集合S中顶点相连的最小边权
3. 重复以下步骤直到所有顶点都被选择：
   • 在未选择的顶点中找出key值最小的顶点u，将u加入S
   • 更新所有与u相邻的未选择顶点v的key值

代码实现

Prim算法有朴素实现和堆优化两个版本，下面是堆优化的实现：

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, weight;
    Edge(int _to, int _w) : to(_to), weight(_w) {}
};

vector<Edge> graph[MAXN];  // 邻接表表示的图
bool visited[MAXN];        // 记录顶点是否已加入MST
int key[MAXN];             // key[i]表示顶点i与已选顶点集合相连的最小边权

int prim(int n) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        key[i] = INF;
        visited[i] = false;
    }

    // 从顶点1开始
    key[1] = 0;

    // 使用优先队列（小顶堆）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});  // {key值, 顶点编号}

    int totalWeight = 0;
    int vertexCount = 0;  // 记录已加入MST的顶点数

    while (!pq.empty() && vertexCount < n) {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if (visited[u]) continue;

        visited[u] = true;
        totalWeight += w;
        vertexCount++;

        // 更新u的所有邻接点的key值
        for (const Edge& e : graph[u]) {
            int v = e.to;
            int weight = e.weight;

            if (!visited[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
            }
        }
    }

    // 检查是否所有顶点都已加入MST
    return (vertexCount == n) ? totalWeight : -1;  // -1表示图不连通
}

时间复杂度分析

• 堆优化的Prim算法时间复杂度：O(E log V)
• 朴素Prim算法时间复杂度：O(V²)

Kruskal vs Prim：算法对比

特殊情况处理

次小生成树

次小生成树是指权值和仅次于最小生成树的生成树。求解次小生成树的步骤：

1. 找出最小生成树T
2. 对于T中的每条边e：
   • 暂时移除e
   • 在不考虑e的情况下，找出连接e两端点的最小权边e'（e'不在T中）
   • 计算T - e + e'的总权值
3. 所有可能替换方案中，权值和最小的即为次小生成树

最小生成森林

当图不连通时，我们需要求解最小生成森林，即每个连通分量的最小生成树的集合。Kruskal算法自然支持求解最小生成森林。

应用场景

1. 网络设计：设计成本最低的网络连接方案
2. 电路布线：寻找最短的布线方式
3. 聚类算法：如连通图的单链接聚类
4. 近似算法：用于解决旅行商问题的近似算法

习题推荐

1. POJ 1287 Networking（基础MST练习）
2. POJ 1789 Truck History（Kruskal实践）
3. POJ 2485 Highways（Prim算法实践）
4. POJ 1679 The Unique MST（判断MST是否唯一）
5. POJ 3723 Conscription（最大生成树的应用）

解题技巧

1. 预处理：处理复杂问题时，可能需要先将问题转化为标准MST问题
2. 完全图构造：有时需要构建完全图，然后求MST
3. 离线处理：当边的信息不同时给出时，可以先存储所有信息再处理
4. 最大生成树：只需将所有边权取负，然后求最小生成树即可