生成树理论

本文基于我个人对生成树的理解：在保留连通性的前提下，尽可能删掉原图里多余的边。

本篇只整理生成树本身的理论。虚拟节点、瓶颈询问、严格次小生成树、特殊边数量限制、隐式完全图等具体问题，放到 生成树题型整理 中继续展开。

一、生成树到底在保留什么

一个有 $n$ 个点的连通图，至少需要 $n-1$ 条边才能保持连通。因为每加入一条连接两个不同连通块的边，连通块数量最多减少 $1$，所以至少需要做 $n-1$ 次有效合并。

反之，如果一个连通图中存在环，由于删掉环上任意一条边以后，被删边的两个端点仍然可以沿环的另一侧互相到达，所以整体连通性不会被破坏。也就是说，只要还有环，就存在“连通意义上的冗余边”，一直删到不能再删，就得到了一棵树。

至此，我认为生成树的核心在于：它刚好用最少的边保留了原图的全局连通性，因此也可以把它理解成原图的一副连通骨架。

如果原图本身不连通，那么每个连通分量各自留下这样的骨架，得到的就是生成森林。

最小生成树

既然同一个图通常有很多棵生成树，那么自然就会产生疑问：选哪一棵？

如果每条边有权值，要求生成树的总边权最小，就是最小生成树 MST；反过来要求最大，就是最大生成树 MaxST。

MST 的定义为：在所有生成树中，找总边权最小的一棵，它本身并不要求边权非负。

如果一个原问题允许选择任意连通子图，并且额外保留边只会增加或不改变代价，那么有环就可以继续删边，最终总能得到一棵不更差的生成树。

但如果额外选择某条边本身可能带来收益，例如负代价边，那么最优连通子图不一定是一棵树，这时就不能直接把问题等价成 MST。

二、如何求最小生成树

知道 MST 是什么以后，下一个自然的问题就是：如何从所有生成树中选出最小的那一棵？

常见做法主要有三种：Kruskal、Prim 和 Borůvka。算法竞赛中最常用的仍然是 Kruskal；Prim 更多是一种不同的选边视角，而 Borůvka 则在一些无法直接枚举全部边的问题中更有价值。

Kruskal

Kruskal 的过程最直接：

1. 将所有边按照权值从小到大排序；
2. 依次考虑每条边；
3. 如果这条边连接两个不同连通块，就加入，否则跳过；
4. 直到已经选择 $n-1$ 条边。

这里的并查集维护的是当前已经选出的森林中，各个点分别属于哪个连通块。

所以 Kruskal 可以先理解成：按边权从小到大扫描，不断选择能够让两个当前连通块发生合并的边。

▶

Kruskal

struct DSU { /* 模板代码略 */ } dsu;

struct Edge { 
    int u, v; ll w;
    bool operator < ( const Edge &oth ) const { return w < oth.w; }
};

vector<Edge> edge;

void init( int M = 0 ) {
    edge.clear( );
    if( M ) edge.reserve( M );
}

void add_edge( int u, int v, ll w ) {
    edge.push_back({ u, v, w });
}

// 返回 inf 表示不连通
ll kruskal( int N ) {
    dsu.init( N );
    sort( edge.begin( ), edge.end( ) );

    ll res = 0;
    int cnt = 0;

    for( auto [u, v, w] : edge ) {
        if( !dsu.merge( u, v ) ) continue;
        res += w;
        if( ++ cnt == N - 1 ) break;
    }

    if( cnt != N - 1 ) return inf;
    return res;
}

Prim

Prim 不再同时维护许多连通块，而是始终维护一个已经加入生成树的点集 $S$，每次选择连接 $S$ 与 $V-S$ 的最轻边，把一个新点接进来。

所以 Prim 可以理解成：固定一个不断扩张的连通块，每次选择它通向外部的最轻边。

在算法竞赛中，Prim 很少具有不可替代性。它更重要的意义是展示了另一种基于割的贪心方式；真正实现时，主要根据图的稠密程度选择朴素版或堆优化版。

朴素 Prim

朴素 Prim 使用邻接矩阵，维护每个未加入点到当前点集 $S$ 的最小连接边，每轮再从这些点中找到 dis 最小的点加入。

时间复杂度为 $\mathcal O(n^2)$，更适合稠密图或点数较小的情况。

▶

朴素 Prim

ll g[maxn][maxn], dis[maxn];
bool vis[maxn];

void init( int N ) {
    for( int i = 1; i <= N; ++ i ) {
        for( int j = 1; j <= N; ++ j ) {
            g[i][j] = ( i == j ? 0 : inf );
        }
    }
}

void add_edge( int u, int v, ll w ) {
    g[u][v] = min( g[u][v], w );
    g[v][u] = min( g[v][u], w );
}

// 返回 inf 表示不连通
ll prim( int S, int N ) {
    fill( dis + 1, dis + N + 1, inf );
    fill( vis + 1, vis + N + 1, false );

    dis[S] = 0;
    ll res = 0;

    for( int i = 1; i <= N; ++ i ) {
        int u = -1;

        for( int v = 1; v <= N; ++ v ) {
            if( vis[v] ) continue;
            if( u == -1 || dis[v] < dis[u] ) u = v;
        }

        if( u == -1 || dis[u] == inf ) return inf;

        vis[u] = true;
        res += dis[u];

        for( int v = 1; v <= N; ++ v ) {
            if( !vis[v] ) dis[v] = min( dis[v], g[u][v] );
        }
    }

    return res;
}

堆优化 Prim

如果使用邻接表，只在加入新点时更新它的相邻点，并使用优先队列维护当前最小的 dis，复杂度可以做到 $\mathcal O(m\log n)$。

▶

堆优化 Prim

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

ll dis[maxn];
bool vis[maxn];

void init( int N ) {
    for( int i = 1; i <= N; ++ i ) adj[i].clear( );
}

void add_edge( int u, int v, ll w ) {
    adj[u].push_back({ v, w });
    adj[v].push_back({ u, w });
}

struct State {
    int u; ll d;
    bool operator < ( const State &oth ) const { return d > oth.d; }
};

// 返回 inf 表示不连通
ll prim( int S, int N ) {
    fill( dis + 1, dis + N + 1, inf );
    fill( vis + 1, vis + N + 1, false );

    priority_queue<State> pq;
    dis[S] = 0;
    pq.push({ S, 0 });

    ll res = 0;
    int cnt = 0;

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

        if( vis[u] ) continue;

        vis[u] = true;
        res += d;
        ++ cnt;

        for( auto [v, w] : adj[u] ) {
            if( vis[v] || w >= dis[v] ) continue;
            dis[v] = w;
            pq.push({ v, dis[v] });
        }
    }

    if( cnt != N ) return inf;
    return res;
}

Borůvka

Borůvka 则让所有当前连通块一起工作。

每一轮中，每个连通块分别选择自己通向外部的最轻边，再利用这些边尽可能合并当前连通块。

如果一轮开始时有 $k$ 个连通块，那么合并后每个新的连通块至少包含两个旧连通块，因此连通块数量至多变成原来的一半，整个算法只有 $\mathcal O(\log n)$ 轮。

相比于把 Borůvka 当作另一份常规 MST 模板，它更适合作为一种框架：只要能够快速求出每个当前连通块的最轻出边，就可以继续完成 MST，而不一定需要显式得到全部边。

不同连通块选择出的最轻出边可能重复，在等权情况下也可能产生冗余，因此这些边更准确地说法是本轮的安全候选。实际加入时仍然需要通过 DSU 判断它是否真的连接两个不同的当前连通块。

下面的代码只保留 Borůvka 的通用框架，需要根据题目设计“寻找最小出边”的部分。

▶

Borůvka

struct Edge { int u, v; ll w; };

// best[rt]: 本轮开始时，连通块 rt 的最小出边。
Edge best[maxn];

// roots: 本轮开始时的所有连通块根。
vector<int> roots;

// comp[rt]: 本轮开始时，连通块 rt 包含的所有节点。
vector<int> comp[maxn];

// 返回 inf 表示不连通
ll boruvka( int N ) {
    dsu.init( N );

    ll res = 0;
    int cnt = N;

    while( cnt > 1 ) {
        roots.clear( );
        for( int i = 1; i <= N; ++ i ) comp[i].clear( );

        // 固定本轮开始时的 DSU 状态。
        for( int u = 1; u <= N; ++ u ) {
            int rt = dsu.find( u );
            comp[rt].push_back( u );
        }

        for( int i = 1; i <= N; ++ i ) {
            if( dsu.find( i ) != i ) continue;
            roots.push_back( i );
            best[i] = { -1, -1, inf };
        }

        /* ----------------------------------------
         * 题目特化区：
         * 对每个 rt ∈ roots，寻找从 comp[rt]
         * 连向其他连通块的最小边 (u, v, w)，
         * 并更新 best[rt]。
         * ---------------------------------------- */

        int merged = 0;

        for( int rt : roots ) {
            if( best[rt].u == -1 ) continue;

            auto [u, v, w] = best[rt];
            if( !dsu.merge( u, v ) ) continue;

            res += w;
            -- cnt;
            ++ merged;
        }

        if( merged == 0 ) return inf;
    }

    return res;
}

Summary

三种算法可以先作如下区分：

• Kruskal：边驱动，全局按权值推进并合并多个连通块；
• Prim：单连通块驱动，不断扩张当前生成树；
• Borůvka：连通块驱动，所有当前连通块并行寻找最轻出边。

它们的写法不同，但为什么这些贪心都正确，还需要更底层的生成树性质。

三、生成树交换与 MST 的正确性

交换结构

先不考虑边权，只看一棵普通生成树。

如果向树中加入一条非树边 $e=(u,v)$，由于树上 $u,v$ 之间原本只有一条路径，所以会产生一个唯一的环。从这个环上删除任意一条原来的树边，就又会得到一棵生成树。

反过来，如果删除一条树边，原树会分裂成两个连通块。重新加入任意一条跨过这两个连通块的边，也会恢复成一棵生成树。

所以生成树之间最基本的变化就是：加入一条边形成环，再删除环上一条边。

生成树结构决定了“能不能这样换”，MST 的边权最优性再决定“该不该这样换”。

割性质

[[图论基本概念#割|割]] 的具体定义放在图论基本概念中讨论，这里只关心它与 MST 的关系。

考虑一个割 $(S,V-S)$，设 $e$ 是跨过这个割的 最轻边。

如果某棵 MST $T$ 已经包含 $e$，自然没有问题。

如果 $T$ 不包含 $e$，就把 $e$ 加进去，此时会产生唯一的环。因为 $e$ 从割的一边走到另一边，所以这个环要回到起点，就一定还会经过另一条跨割边 $f$。

由于 $e$ 是这个割上的最轻边，所以有 $w(e)\le w(f)$。

此时结合交换结构，删掉 $f$、保留 $e$ 后，仍然是一棵生成树，并且总边权不会更大。

因此：一个割上的最轻边至少可以出现在某一棵 MST 中。

这就是割性质，这里所谓“安全”，指的是选择这条边以后，仍然存在某棵 MST 能够包含当前已经做出的选择，不会因为这次贪心而失去最优解。

如果 $e$ 是这个割上唯一的最轻边，那么任何不包含 $e$ 的生成树都可以通过交换严格变轻，所以 $e$ 会出现在所有 MST 中。

Kruskal 的正确性

现在再回头看 Kruskal。

如果当前边 $e=(u,v)$ 的两个端点已经属于同一个连通块，那么把它加入当前森林时就会形成环。

而由于 Kruskal 按边权从小到大扫描，当前的 $e$ 一定是这个环上的最大边之一，因此没有必要保留它，这也解释了为什么连通时直接跳过这条边。

如果 $u,v$ 属于两个不同连通块，取其中一个当前连通块 $A$，考虑割 $(A,V-A)$。

当前已经选中的边不可能跨过这个割，否则割外的点早就应该属于 $A$。

此外，当前边 $e$ 一定是这个割上的最轻边之一。否则若存在更轻的跨割边 $f$，它应该更早被 Kruskal 扫到，而当时 $f$ 的两个端点同样不可能已经连通，于是 $f$ 会被选入并提前合并这两个部分，与当前 $A$ 仍然是一个独立连通块矛盾。

所以根据割性质，$e$ 可以安全加入。

因此更严谨的解释是：森林结构 保证加入跨连通块边后仍然合法，而 割性质 保证优先选择其中的轻边不会丢失最优解。

Prim 与 Borůvka 的正确性

Prim 当前维护的点集 $S$ 始终连通，所以 $(S,V-S)$ 本身就是一个自然的割。它每次选择这个割上的最轻边，因此直接由割性质保证正确。

Borůvka 同理。对每个当前连通块 $C$，考虑割 $(C,V-C)$。该连通块的最轻出边就是这个割上的最轻边，因此也是安全边。

因此 Kruskal、Prim、Borůvka 虽然写法不同，但三者的正确性都可以统一到 割性质 上。

环性质

割性质是从“什么边可以安全加入”出发。

反过来，如果考虑一个环，并且其中某条边 $e$ 严格大于环上其他所有边，那么 $e$ 不可能出现在任何 MST 中。

假设某棵 MST 包含 $e$。删掉 $e$ 后，树被分成两个连通块，而原环上剩余路径一定还存在另一条跨过这两个连通块的边 $f$，并且 $w(f)<w(e)$。

用 $f$ 替换 $e$ 后，可以得到一棵更轻的生成树，与 MST 最优矛盾。

所以环性质就是：环上的严格最大边不属于任何 MST。

如果最大权边存在并列，那么这些等权边之间可能存在零代价替换，此时不能直接说所有最大边都不在 MST。

因此割性质和环性质可以看成同一个交换动作的两个方向：割性质偏向“安全加入”，环性质偏向“安全排除”。

四、Kruskal & 权值阈值

由于 Kruskal 选边是按权值从小到大处理的，所以它还隐式地记录了：

当允许使用的最大边权不断变大时，原图中的连通块怎样逐渐合并。

设当前只允许使用权值不超过 $W$ 的边。

随着 $W$ 增大，可以使用的边越来越多，所以连通块只会不断合并。

对于两个点 $u,v$，存在一个最小的阈值 $W$，使得只允许使用权值不超过 $W$ 的边时，$u,v$ 第一次变得连通。

这个 $W$ 就是：$\displaystyle W = \min_P \max_{e\in P} w(e)$，其中 $P$ 枚举所有 $u\to v$ 路径。

所以最小化路径最大边权的问题也等价为：两点第一次连通需要把允许边权放宽到多少。

这就是常见的 minimax 瓶颈路问题。

MST 的瓶颈性质

如果 $T$ 是任意一棵 MST，那么 $T$ 上 $u\to v$ 路径中的最大边权，也恰好等于这个 minimax 值。

真正的原因仍然是交换。

设 MST 上 $u\to v$ 路径的最大边为 $e$，权值为 $W$。如果原图存在另一条 $u\to v$ 路径，其所有边权都严格小于 $W$，那么删掉 $e$ 后会形成一个割，而这条更优路径中一定存在一条跨割边 $f$，满足 $w(f)<w(e)$。

此时用 $f$ 替换 $e$，就会得到一棵更轻的生成树，与 MST 本身矛盾。

因此：任意 MST 上的 $u\to v$ 路径，都会实现 $\displaystyle \min_P\max_{e\in P}w(e)$。

不同 MST 的具体路径可能不同，但这个瓶颈值相同，因为它由原图本身决定。

进一步地，如果一棵生成树对任意两个点都实现了原图的 minimax 值，那么它本身也一定是 MST。等价地说，对任意非树边 $e=(u,v)$，树上 $u\to v$ 路径的最大边权都不能超过 $w(e)$。这一点会在第六节重新出现。

对应地，maximin 瓶颈 $\displaystyle \max_P\min_{e\in P}w(e)$ 同理可以通过最大生成树处理。

五、Kruskal 重构树

前面提到，Kruskal 的过程可以理解成“连通块随着权值阈值不断合并”。那么自然会产生一个问题：

能不能把这些合并过程本身保存下来呢？

普通 Kruskal 每成功合并两个连通块，只执行一次 merge，之后这次合并本身就不再保留。

如果在每次合并成功时新建一个节点，记录本次合并的边权，再把原来的两个连通块挂到这个新节点下面，就得到了 Kruskal 重构树 KRT。

在 KRT 上，原图的顶点是叶子，内部节点代表一次连通块合并，权值则表示发生这次合并时的阈值。

最小生成树方向下，Kruskal 按边权从小到大处理，因此从叶子向根走时，节点权值单调不减。

对于两个原图顶点 $u,v$，它们在重构树上的 LCA，恰好对应第一次把 $u,v$ 合并进同一个连通块的那次事件。

因此：LCA 的权值就是使 $u,v$ 连通所需的最小边权阈值，也就是 minimax 值。

这同样给出了一种处理瓶颈路的方法。

普通 MST 和 Kruskal 重构树保存的是同一类信息，但表示方式不同：

• 普通 MST 保存真实选边，通过树上路径最大值读取瓶颈；
• Kruskal 重构树保存合并层次，通过 LCA 读取首次连通阈值。

不过这里要注意：Kruskal 重构树本身不是原图的一棵生成树！它记录的是 Kruskal 的连通块合并历史。

至于 KRT 如何进一步处理阈值连通块、子树信息等问题，仍留待独立专题建立后再展开。

六、固定一棵 MST 以后还能得到什么

前面的 Kruskal、Prim、Borůvka 都在解决“如何找到一棵 MST”。

如果已经确定了一棵 MST，接下来自然会问：

其他生成树和这棵 MST 之间有什么关系？

基本环与基本割

固定一棵生成树 $T$。

对于一条非树边 $e=(u,v)$，加入以后形成的唯一环，称为 $e$ 关于 $T$ 的 基本环。

反过来，删除一条树边 $f$ 后，树会分成两个连通块，由这两个点集形成的割称为 $f$ 关于 $T$ 的 基本割。

于是换边有两个完全对应的视角：

• 加入非树边，在基本环里找一条树边删掉；
• 删除树边，在基本割里找一条非树边补回来。

所以固定一棵生成树以后，其他生成树可以通过这种一进一出的交换逐渐得到。

MST 的一个等价交换条件

设 $e=(u,v)$ 是一条非树边，令 $M$ 为 $T$ 上 $u\to v$ 路径中的最大边权。

如果 $w(e)<M$，那么加入 $e$，再删除路径上的最大边，就能得到一棵更轻的生成树。

所以如果 $T$ 是 MST，则一定有：$w(e)\ge M$。

也就是说：对任意非树边，它都不会比自己基本环上的最大树边更轻。

反过来，如果一棵生成树对所有非树边都满足这个条件，那么就不存在一次能够让它变轻的基本环交换，而这也足以推出它本身就是 MST。

因此这个条件既可以看成 MST 最优性的一个交换判定，也可以看成上一节瓶颈性质的另一种表达。

MST 唯一性

MST 的结构可能不唯一，但最小总权值这个数值一定唯一。

是否存在多棵 MST，本质上取决于：有没有一次代价为 $0$ 的合法换边。

如果存在一条非树边 $e$，其权值刚好等于基本环上的最大树边 $f$，那么用 $e$ 替换 $f$ 后：$w(e)-w(f)=0$，就会得到另一棵同权 MST。

所以如果存在零代价基本环交换，MST 就不唯一。

反过来，如果对所有非树边 $e=(u,v)$，都有：$\displaystyle w(e)>\max_{f\in P_T(u,v)}w(f)$，那么任何一次换边都会使总权值严格增加，因此不存在另一棵同权 MST。

注：“所有边权互不相同”只是一个常见的充分条件，不是必要条件。存在重复边权，也并不意味着一定存在能够零代价交换的边。

至于进一步判断哪些边属于所有 MST、哪些只属于部分 MST、哪些不属于任何 MST，已经属于更具体的应用，放到 生成树题型整理 中讨论。

七、算法选择与边界

显式边图中，Kruskal 通常是最自然的默认选择。它实现简单，容易和并查集、生成森林、边分类、权值参数化等结构继续组合，所以大多数常规 MST 问题都可以优先考虑它。

Prim 更适合从“维护一个不断扩张的连通块”这一视角理解。朴素 Prim 在稠密图、邻接矩阵或点数较小时仍然很自然；堆优化 Prim 在一般稀疏图上虽然同样可用，但多数情况下并没有比 Kruskal 更强的不可替代性。

Borůvka 的价值主要体现在边无法直接枚举时。它不要求先得到完整边序，只要求能够在每一轮为当前连通块找到最轻出边，因此常被用来承接一些具有特殊边权结构的隐式图问题。

三种算法真正依赖的信息并不完全相同：

• Kruskal 需要能够按权值处理候选边；
• Prim 需要维护当前点集到外部的最轻连接；
• Borůvka 需要为每个当前连通块找到最轻出边。

因此，如果原图的边无法显式建立，此时问题就转化为了：能不能利用边权结构，直接提供算法真正需要的安全边信息？

具体的隐式完全图、候选边稀疏化、隐式 Kruskal 与 Borůvka 应用，继续放在 生成树题型整理 中展开。

八、小结

摘要

生成树负责保留连通性，交换结构负责描述生成树之间怎样变化，MST 则在这些合法交换上加入边权最优性。

Kruskal、Prim、Borůvka 的区别主要在于怎样寻找下一条安全边，其中 Kruskal 是最常用的基础实现，Borůvka 则提供了“按连通块寻找最轻出边”的另一种接口。

从 Kruskal 的权值推进继续观察，可以得到两点第一次连通的阈值，并由此得到 MST 的瓶颈性质；Kruskal 重构树则进一步把这些连通块合并事件保存成树。

固定一棵 MST 后，基本环与基本割描述了生成树之间的局部交换，而 MST 唯一性本质上取决于是否存在零代价换边。

关联

• 具体建模见 生成树题型整理。
• 树上路径接口见 LCA 体系。
• 图论导航见 20_图论。