基础概念与问题定义

在图论中，给定一个连通的无向加权图，其生成树是指包含图中所有顶点且恰好包含 $n-1$ 条边的子图，该子图构成一棵无环的树结构。若图中所有可能的生成树里，边权总和最小，则该树被称为最小生成树（Minimum Spanning Tree, MST）。MST 问题在通信网络布线、交通规划及数据聚类等领域具有核心地位。

核心算法解析

Kruskal 算法

Kruskal 算法基于贪心策略与并查集（Disjoint Set Union）数据结构。其执行逻辑是将图中所有边按权重升序排序，随后依次遍历排序后的边集。对于每条边，若其连接的两个顶点分属不同的连通分量，则合并这两个分量并将该边纳入生成树；若两端点已连通，则舍弃该边以防止环路产生。当成功选入 $n-1$ 条边时，算法终止。

正确性简述： 该算法在每一步均选择当前未处理边中权值最小且不会构成环的边。根据图的割性质（Cut Property），对于任意一个将顶点集划分为两部分的割，跨越该割且权值最小的边必然属于某棵最小生成树。通过数学归纳法可严格证明，该贪心策略始终保持当前边集是全局最优解的子集。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

struct EdgeLink {
    int source, target, weight;
    bool operator<(const EdgeLink& other) const {
        return weight < other.weight;
    }
};

class UnionFindSet {
    vector<int> parent_node, rank_level;
public:
    explicit UnionFindSet(int size) : parent_node(size), rank_level(size, 0) {
        iota(parent_node.begin(), parent_node.end(), 0);
    }
    int find_root(int node) {
        if (parent_node[node] != node)
            parent_node[node] = find_root(parent_node[node]);
        return parent_node[node];
    }
    bool merge_components(int u, int v) {
        int root_u = find_root(u), root_v = find_root(v);
        if (root_u == root_v) return false;
        if (rank_level[root_u] < rank_level[root_v]) swap(root_u, root_v);
        parent_node[root_v] = root_u;
        if (rank_level[root_u] == rank_level[root_v]) ++rank_level[root_u];
        return true;
    }
};

long long computeKruskal(int vertex_cnt, int edge_cnt, const vector<EdgeLink>& edges) {
    vector<EdgeLink> sorted_list = edges;
    sort(sorted_list.begin(), sorted_list.end());

    UnionFindSet dsu(vertex_cnt + 1);
    long long accumulated_weight = 0;
    int edges_selected = 0;

    for (const auto& current_edge : sorted_list) {
        if (dsu.merge_components(current_edge.source, current_edge.target)) {
            accumulated_weight += current_edge.weight;
            if (++edges_selected == vertex_cnt - 1) break;
        }
    }
    return (edges_selected == vertex_cnt - 1) ? accumulated_weight : -1;
}

Prim 算法

Prim 算法采用另一种贪心视角：维护一个已接入生成树的顶点集合 $V_{in}$，初始状态仅包含任意一个起始节点。在每一轮迭代中，算法寻找所有连接 $V_{in}$ 与 $V_{out}$（未接入集合）的边中权重最小的一条，将其对应的外部顶点并入 $V_{in}$，并同步更新相关顶点的最近距离。该过程与 Dijkstra 最短路径算法高度相似，均可借助优先队列实现堆优化。

正确性简述： 算法每次扩张均选择当前割的最小权边。假设存在更优的生成树不包含该边，则将其替换进最优树后必然产生更小权值的生成树或保持相等，这与最小生成树的定义矛盾，从而证明贪心选择的局部最优可导向全局最优。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct QueueElement {
    int target_vertex;
    int edge_cost;
    bool operator>(const QueueElement& other) const {
        return edge_cost > other.edge_cost;
    }
};

long long computePrim(int total_vertices, int start_node, const vector<vector<pair<int, int>>& adjacency) {
    vector<int> min_dist(total_vertices + 1, INT_MAX);
    vector<bool> visited(total_vertices + 1, false);
    priority_queue<QueueElement, vector<QueueElement>, greater<QueueElement>> pq;

    min_dist[start_node] = 0;
    pq.push({start_node, 0});

    long long mst_total = 0;
    int nodes_covered = 0;

    while (!pq.empty() && nodes_covered < total_vertices) {
        auto [current_node, current_weight] = pq.top();
        pq.pop();

        if (visited[current_node]) continue;
        visited[current_node] = true;
        mst_total += current_weight;
        ++nodes_covered;

        for (const auto& [neighbor, edge_w] : adjacency[current_node]) {
            if (!visited[neighbor] && edge_w < min_dist[neighbor]) {
                min_dist[neighbor] = edge_w;
                pq.push({neighbor, edge_w});
            }
        }
    }
    return (nodes_covered == total_vertices) ? mst_total : -1;
}

典型问题模型与变体

虚拟源点建图模型

部分优化问题允许通过引入额外的虚拟节点来统一建图逻辑。例如，当每个独立元素可选择固定成本 $A$ 单独获取，或通过折扣关系与其他元素关联购买时，可构造一个虚拟根节点，将其与所有实际节点相连，边权设为 $A$。其余折扣关系作为实际边权。原问题随即转化为求解包含该虚拟节点的最小生成树。

连通块数量限制

若业务场景要求最终图结构划分为 $k$ 个独立连通分量而非单棵树，可在 Kruskal 算法执行阶段设置提前终止条件。当成功合并的边数达到 $n - k$ 时停止遍历，下一条待处理边的权重即为各连通分量间的最小间隔阈值。该模型广泛适用于聚类分析与资源分区。

瓶颈路径判定

在路径规划中，若需最小化路径上的最大边权（即寻找瓶颈容量最小化路径），可直接利用 MST 的割性质：任意两点在 MST 路径上的最大边权，必然等于原图中所有可能路径的瓶颈最小值。通过按边权排序并逐步合并连通分量，直到指定两点首次连通，即可直接获取该瓶颈值。

特殊图结构的 MST 求解

有向图的最小树形图（特定约束简化）

对于有向图，若需构造以某点为根的生成树且边方向必须遵循特定拓扑（如仅允许从高海拔指向低海拔），问题可简化为定向生成树求解。可先通过深度优先搜索筛选合法边集，随后按照终点海拔降序、边权升序的双关键字规则执行类 Kruskal 合并。该排序策略可确保父节点总是先于子节点被处理，从而保证方向合法性与权重最优性。

网格图优化

在规则网格图中，横向边与纵向边的权重通常分别独立分布。利用 Kruskal 的贪心特性，可将所有横边与纵边分别排序。设当前已选横边 $h$ 条、纵边 $v$ 条，下一次添加一条横边可消除 $(m-1-h)$ 个水平连通断层，纵边同理。通过双指针交替选取最小权重边并累加其对连通性的贡献值，可将时间复杂度优化至 $O(N \log N + M \log M)$。

完全图与增量构造

当图结构为完全图且边权遵循特定数学规律时，可直接推导闭式解。例如，每增加若干顶点使其构成完全子图，新增边数满足二次多项式关系。通过求解一元二次方程确定完整完全子图的顶点数，剩余顶点按线性规则连接，即可在常数时间内计算总权重，避免显式建图带来的空间爆炸。

严格次小生成树

次小生成树要求权值和严格大于最小生成树且为所有可能结构中的最小值。核心性质在于：次小生成树与最小生成树仅相差一条边的交换。标准求解流程如下：

1. 首先计算原图的最小生成树 $T_{min}$，记录其总权值 $W$。
2. 枚举所有非树边 $(u, v)$，计算将其加入 $T_{min}$ 后形成的唯一环路。
3. 查找该环上权值最大的边 $e_{max}$ 与严格次大边 $e_{sec}$。
4. 若 $weight(u, v) \neq weight(e_{max})$，则候选值为 $W + weight(u, v) - weight(e_{max})$；否则候选值为 $W + weight(u, v) - weight(e_{sec})$。

环上最值查询可通过树上倍增（Binary Lifting）高效维护。每个节点向上跳跃 $2^i$ 步时，同步记录路径上的最大值与严格次大值。合并两段路径信息时，需将四个候选值排序去重，以确保严格次大值的准确性。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int MAX_LOG = 20;
struct GraphEdge { int u, v, w; };

// 倍增数组：祖先节点、路径最大值、路径严格次大值
int ancestor[100005][MAX_LOG], path_max[100005][MAX_LOG], path_sec[100005][MAX_LOG];
int node_depth[100005];
vector<pair<int, int> tree_graph[100005];

pair<int, int> combine_intervals(pair<int, int> left, pair<int, int> right) {
    int candidates[4] = {left.first, left.second, right.first, right.second};
    sort(candidates, candidates + 4, greater<int>());
    int peak = candidates[0];
    int strict_peak = -INT_MAX;
    for (int val : candidates) {
        if (val != peak) { strict_peak = val; break; }
    }
    return {peak, strict_peak};
}

void build_doubling(int curr, int parent, int depth, int weight_to_parent) {
    node_depth[curr] = depth;
    ancestor[curr][0] = parent;
    path_max[curr][0] = weight_to_parent;
    path_sec[curr][0] = -INT_MAX;
    for (int step = 1; step < MAX_LOG; ++step) {
        int mid = ancestor[curr][step-1];
        ancestor[curr][step] = ancestor[mid][step-1];
        auto merged = combine_intervals({path_max[curr][step-1], path_sec[curr][step-1]},
                                        {path_max[mid][step-1], path_sec[mid][step-1]});
        path_max[curr][step] = merged.first;
        path_sec[curr][step] = merged.second;
    }
    for (auto &[next_node, w] : tree_graph[curr]) {
        if (next_node != parent) build_doubling(next_node, curr, depth + 1, w);
    }
}

pair<int, int> extract_path_stats(int start, int end) {
    if (node_depth[start] < node_depth[end]) swap(start, end);
    pair<int, int> result = {0, -INT_MAX};
    for (int step = MAX_LOG - 1; step >= 0; --step) {
        if (node_depth[ancestor[start][step]] >= node_depth[end]) {
            result = combine_intervals(result, {path_max[start][step], path_sec[start][step]});
            start = ancestor[start][step];
        }
    }
    if (start == end) return result;
    for (int step = MAX_LOG - 1; step >= 0; --step) {
        if (ancestor[start][step] != ancestor[end][step]) {
            result = combine_intervals(result, {path_max[start][step], path_sec[start][step]});
            result = combine_intervals(result, {path_max[end][step], path_sec[end][step]});
            start = ancestor[start][step];
            end = ancestor[end][step];
        }
    }
    result = combine_intervals(result, {path_max[start][0], path_sec[start][0]});
    result = combine_intervals(result, {path_max[end][0], path_sec[end][0]});
    return result;
}

上述倍增查询框架可直接嵌入次小生成树的主循环中。遍历所有未入选的边，调用路径统计函数获取环上极值，计算替换后的权值差并取全局最小值，即可高效得出严格次小生成树的最终结果。