#创作计划#最小生成树

复仇者_天之神_银色子弹

2025-09-29 20:52:12

发布于：浙江

27阅读

0回复

0点赞

完结

对于最小生成树，我将会从一下几个角度进行讲解

图：由一组顶点和连接顶点的边组成。
连通图：图中任意两个顶点之间都存在路径。
树：一个没有环的连通图。
生成树：一个连通无向图的生成树是它的一个连通子图，它包含原图的所有顶点，但边数最少（恰好有 $n-1$ 条边，其中 $n$ 是顶点数），并且没有环。

简单来说，生成树就是用最少的边把图中所有的顶点都连通起来，并且保证没有回路。

举个例子：
想象一个城市网络，每个顶点代表一个城市，边代表城市之间的道路。这个城市网络本身可能有很多条路，甚至有多条路连接相同的两个城市（形成环）。那么，这个网络的一个“生成树”就是一套能让你从任何一个城市开车到任何其他城市，且道路数量最少的路线规划。这套规划里不会有“环路”或“冗余的道路”。

现在，我们给图的每条边加上一个权重的概念。权重可以代表距离、成本、时间等。
最小生成树就是：在一个带权连通无向图中，总权重和最小的那棵生成树。

继续上面的例子：
现在每条道路（边）都有修建成本（权重）。我们想找出一套道路规划，既能连接所有城市（生成树），又使得总的修建成本最低。这套规划就是这个城市网络的最小生成树。

核心目标：在保证所有点连通的前提下，选择总权重最低的边。

三、最小生成树的性质

唯一性：最小生成树不一定唯一。当图中存在多条权重相同的边，并且可以互换时，就可能产生多个不同的最小生成树，但它们的总权重是相同的。
边数：任何最小生成树都必然包含恰好 $n-1$ 条边（ $n$ 是顶点数）。
环性质：在最小生成树中，任意加上一条原本不在树中的边，都会形成一个环。并且这个环上新加入的那条边，一定是环上权重最大的边（否则就可以用它替换掉环上更大的边，得到更小的总权重，与“最小”矛盾）。
切割性质：把图的顶点分成任意两个集合（一个切割），连接这两个集合的权重最小的边，必然属于图的最小生成树。

四、算法---Kruskal

核心思想：将所有边按权重从小到大排序，然后依次考虑每条边。如果加入当前边不会与已选择的边形成环，就将其加入生成树；否则就跳过。

排序：把所有边按权重从低到高排好。
检查：从权重最低的边开始检查，如果加上这条边不会使原来的树形成自环，就加入这条边
重复：直到修好了 $n-1$ 条路。

关键技术：如何高效判断加入一条边是否会形成环？使用并查集数据结构。
${\color{yellow} 第一部分没有好好看的只能重看了哈哈哈}$

初始时，每个顶点自成一个集合。
当考虑一条边的起点 $u$ 和终点 $v$ 时，检查 $u$ 和 $v$ 是否在同一个集合中。
如果在，说明加入这条边会形成环，舍弃。
如果不在，则加入这条边，并将 $u$ 和 $v$ 所在的集合合并。

时间复杂度：排序边需要 $O(m\ log\ m)$ ，而并查集操作近乎常数时间，所以主要复杂度为 $O(m\ log\ m)$ ，非常适合稀疏图，其中 $m$ 为边数。

这是一道模板题
题解：

#include<iostream>
#include<algorithm>
using namespace std;
struct node{  //定义结构体，内涵起点、终点、成本
    int a,b,w;
}a[105];
int f[105];
bool cmp(node a,node b){  //排序函数
    return a.w<b.w;
}
int find(int x){  //查找函数
    if(x==f[x]) return f[x];
    return f[x]=find(f[x]);
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=k;i++) cin>>a[i].a>>a[i].b>>a[i].w;
    sort(a+1,a+k+1,cmp);  //按边排序
    long long cnt=0;
    for(int i=1;i<=k;i++){
        if(f[find(a[i].a)]!=f[find(a[i].b)]){  //如果父节点不同（尚未连通）
            f[find(a[i].a)]=find(a[i].b);  //合并节点，使父节点相同（使其连通）
        }
        else cnt+=a[i].w;  //注意这题是求最大值，如果求最小，应将该语句放入if语句中
    }
    cout<<cnt;
    return 0;
}

五、算法---Prim

核心思想：从某一个顶点开始，每次选择一条连接已构建的树 与未加入树的顶点的权重最小的边，并将该边和对应的顶点加入到树中。

起点：随便选一个顶点。
生长：每次从这棵树向外延伸出最小权重的边，把一个新的点连进来。
重复：直到所有的点都被连入这棵树。

适用数据结构：通常使用优先队列（最小堆） 来高效地获取当前可用的最小边。

时间复杂度：
使用邻接矩阵和简单遍历： $O(n²)$ ，适合稠密图。
使用邻接表和二叉堆： $O(m\ log\ n)$ ，适合稀疏图。(一般直接用Kruskal，很少用）

六、附：算法对比

特性	Kruskal	Prim
核心思想	加边法，按权重从小到大选择边	加点法，从一点出发逐步扩张树
数据结构	并查集 + 边排序	优先队列（最小堆）
时间复杂度	$O(m\ log\ m)$	$O(m\ log\ n)$ 或 $O(n²)$
适用场景	稀疏图（边较少时效率很高）	稠密图（边很多时，用邻接矩阵可能更快）
图是否连通	需额外检查是否有 $n-1$ 条边来判断图是否连通	算法过程自然保证连通性