最小生成树（Prim算法、Kruskal算法）
生成树的定义：
生成树是一个连通图G的一个极小连通子图。 包含G的所有n个顶点,但只有n-1条边,并且是连通的。 生成树可由遍历过程中所经过的边组成（有多个）。
最小生成树的定义：
一个带权连通无向图的生成树中，边的权值之和最小的那棵树叫做此图的最小生成树（唯一）。比如在下面的图一中，其最小生成树为图二：
最小生成树的生成算法：
求解最小生成树的算法主要有两个：
1.Prim（普里姆）算法;
2.Kruskal（克鲁斯卡尔）算法。
下面对这两个算法分别进行分析。
—— Prim算法 ——
该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
该算法的描述如下：
- 输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 初始化：定义存放当前已走点的集合Vnew = {x}，其中x为集合V中的任意节点（作为起始点），定义存放当前已走边的集合Enew = { }，为空；
- 重复下列操作，直到 Vnew = V：
① 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
② 将v加入集合Vnew中，将<u, v>边加入集合Enew中； - 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
下面我们用前面的图一来进行举例说明，首先是录入初始图，如下：
其中，当前可选点集U是指与当前已选点集中的点存在可达关系且未被标记为已选的所有点所构成的集合。
接下来我们随机选择一个点作为起点，比如选择V1作为初始点，则需要将V1加入Vnew集合，情况如下：
容易看出，在已选点集和可选点集连接形成的可选边中（<V1 ,V2>，<V1 ,V3>，<V1 ,V4>），边<V1 ,V3>的权值最小，因此需要将边<V1 ,V3>加入Enew集合，同时也需要将点V3加入Vnew集合，此时两个集合的情况如下：
接下来在已选点集和可选点集连接形成的可选边中（<V1 ,V2>，<V1 ,V4>，<V3 ,V2>，<V3 ,V4>，<V3 ,V5>，<V3 ,V6>），选择权值最小的边<V3 ,V6>，将其加入Enew集合，同时将点V6加入Vnew集合，此时两个集合的情况如下：
接着在已选点集和可选点集连接形成的可选边中（<V1 ,V2>，<V1 ,V4>，<V3 ,V2>，<V3 ,V4>，<V3 ,V5>，<V6 ,V4>，<V6 ,V5>），边<V6 ,V4>的权值最小，因此需要将边<V6 ,V4>加入Enew集合，同时也需要将点V4加入Vnew集合，此时两个集合的情况如下：
接着继续在已选点集和可选点集连接形成的可选边中（<V1 ,V2>，<V3 ,V2>，<V3 ,V5>，<V6 ,V5>），选择权值最小的边<V3 ,V2>，并将其加入Enew集合，同时将点V2加入Vnew集合，此时两个集合的情况如下：
接着继续在已选点集和可选点集连接形成的可选边中（<V2 ,V5>，<V3 ,V5>，<V6 ,V5>），选择权值最小的边<V2 ,V5>，并将其加入Enew集合，同时将点V2加入Vnew集合，此时两个集合的情况如下：
至此，集合Vnew = V，即所有的点都已经被选中，故结束循环。
此时，集合Vnew和Enew即可用于描述所得到的最小生成树（如上图中的红色部分）。
下面给出对Prim算法的证明（反证法）：
假设Prim生成的不是最小生成树
- 设Prim生成的树为G0;
- 假设存在Gmin使得cost(Gmin)<cost(G0)，则在Gmin中存在某条边<u,v>不属于G0；
- 将<u,v>加入G0中可得一个环，且<u,v>不是该环的最长边(这是因为<u,v>∈Gmin)；
- 这与Prim每次都选择最短边矛盾，故假设不成立，命题得证。
下面给出用编程语言实现的具体描述（C++）：
/*
// Prim类接受两个参数n,m，分别表示录入的点和边的个数（点的编号从1开始递增）
// 接下来是m行，每行3个数x,y,length，表示点x和点y之间存在一条长度为length的边
// 程序最终会打印出该无向图中的最小生成树的各个边和最小权值
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1010;
struct Node{ //用于构建Node型向量，来存放节点间的可达信息
int node,length; //node表示与某个节点相连接的点，length表示两者之间的长度
Node(){ } //无参构造函数
Node(int a,int b) //构造函数
{ node=a,length=b; }
};
struct Edge{ //用于表示边的信息
int x,y,length; //x,y分别表示某条边两个端点，length则表示这条边的长度
Edge(){ } //无参构造函数
Edge(int a,int b,int c) //构造函数
{ x=a,y=b,length=c; }
};
bool cmp(Edge e1,Edge e2) //用于sort函数排序时的规则
{ return e1.length < e2.length; }
class Prim{ //Prim算法：求解无向连通图中的最小生成树
private:
static const int MAX=N;
vector<Node> v[MAX]; //存放所有节点之间的可达关系与距离(如：v[point][i].node表示节点point和节点node相连、且距离为v[point][i].length)
Edge e[MAX]; //存放与当前已选节点相连的边
vector<Edge> s; //存放最小生成树里的所有边(用向量来表示便于随机访问)
bool vis[MAX]; //标记每个点是否被访问过
int n,m,edgeNum; //n,m分别表示输入的点和边的个数，edgeNum表示当前在e中插入的边数
void insert(int point) //往Vnew中插入一个新的点
{
for(int i=0;i<v[point].size();i++) //则需要将与之相连的所有边插入e
if(!vis[v[point][i].node]) //但是仅需插入没有和那些和已选节点相连的边（从而也是实现了对边的去重）
e[edgeNum++]=Edge(point,v[point][i].node,v[point][i].length); //固定在插入的Edge中，第一个位置x为已访问的点Point，第二个位置y为未访问的点
vis[point]=true; //将该点标记为已走
sort(e,e+edgeNum,cmp); //将边按从小到大的顺序进行排序，方便每次按序访问时得到的边都是当前可选的最小的
}
public:
Prim(int a,int b) //构造函数，参数a,b分别表示录入的无向连通图的节点数和边数
{
n=a,m=b,edgeNum=0;
int x,y,length;
for(int i=0;i<m;i++){
cin>>x>>y>>length;
v[x].push_back(Node(y,length));
v[y].push_back(Node(x,length));
}
}
void run(int start) //执行函数：求解录入的无向连通图的最小生成树
{
insert(start); //参数start表示你选择的随机起点
while(n-s.size()>1) //我们知道，最小生成树的边数=图中节点数-1，因此可以利用这个性质来作为循环条件
{
for(int i=0;i<edgeNum;i++){ //按序遍历所有边
if(!vis[e[i].y]){ //如果待检测的第二个位置上的点未访问过，则说明这条边满足一端在Vnew中，另一端不在
s.push_back(e[i]); //则需要将该边放进结果集合中
insert(e[i].y); //同时将该边的另一个节点插入Vnew中
break; //退出当前搜索
}
}
}
}
void print() //打印函数
{
cout<<"当前录入的总边数为："<<edgeNum<<"\n其中构成最小生成树的边为："<<endl;
int edgeSum=0;
for(int i=0;i<s.size();i++){
cout<<"边 <"<<s[i].x<<","<<s[i].y<<"> = "<<s[i].length<<endl;
edgeSum+=s[i].length;
}
cout<<"最小生成树的权值为："<<edgeSum<<endl;
}
};
int main()
{
int n,m;
cin>>n>>m; //输入无向连通图的节点数和边数
Prim prim(n,m); //构建Prim类
prim.run(1); //开始计算其最小生成树
prim.print(); //打印结果
return 0;
}
比如在程序运行时，输入以下内容（即图一）：
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
则运行后的效果如下：
—— Kruskal算法 ——
该算法由Joseph Kruskal在1956年发表，用来寻找最小生成树。解决同样问题的还有Prim算法和Boruvka算法等，三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。
该算法的描述如下：
- 设无向连通图Graph有v个顶点，e条边；
- 新建图Graphnew，Graphnew拥有与原图中相同的v个顶点，但没有边；
- 将原图Graph中所有边按权值从小到大排序；
- 进入一层循环，该循环从权值最小的边开始遍历每条边，直至图Graphnew中所有的节点都在同一个连通分量中。循环体内的内容如下：
if（这条边连接的两个节点于图Graphnew中不在同一个连通分量中） 则添加这条边到图Graphnew中；
下面我们还是用前面的图一来进行举例说明，首先是将原图中的所有边按权值从小到大进行排序，如下：
然后是建立一个没有任何边的图Graphnew，如下（注：这里的没有边是指没有被描红的边）：
接下来我们开始遍历上面给出的那个表，首先遍历到的第一条边是<V1,V3>，长度为1。由于在当前图中，节点V1和V3并不连通，因此可以将这条边添加到上图中（即标红，下同），如下：
接下来是第二条边<V4,V6>，长度为2。在当前图中，节点V4和V6并不连通，因此可以将这条边添加到上图中，如下：
然后是第三条边<V2,V5>，长度为3。在当前图中，节点V2和V5并不连通，因此可以将这条边添加到上图中，如下：
继续往下是第四条边<V3,V6>，长度为4。在当前图中，节点V3和V6并不连通，因此可以将这条边添加到上图中，如下：
然后是第五条边<V1,V4>，长度为5。注意到在当前图中，节点V1和V4已经在同一个连通分支中，因此不能将这条边添加进来，于是跳过这条边，继续往下。
接着是第六条边<V2,V3>，长度也为5。在当前图中，节点V2和V3并不连通，因此可以将这条边添加到上图中，如下：
至此，我们发现图Graphnew中的所有节点都在同一个连通分支中，因此循环结束。
此时，边集E即可用于描述所得到的最小生成树（如上图中的红色部分）。
下面给出用编程语言实现的具体描述（C++）：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1010;
struct Edge{ //用于表示边的信息
int x,y,length; //x,y分别表示某条边两个端点，length则表示这条边的长度
Edge(){ } //无参构造函数
Edge(int a,int b,int c) //构造函数
{ x=a,y=b,length=c; }
};
bool cmp(Edge e1,Edge e2) //用于sort函数排序时的规则
{ return e1.length<e2.length; }
class UnionFindSet{ //并查集类，用于连通两个节点以及判断图中的所有节点是否连通
private:
static const int MAX=N;
int pre[MAX]; //pre数组用于存放某个节点的上级
int rank[MAX]; //rank数组用于降低关系树的高度
int start,n; //start和n分别用于指示并查集里节点的起点和终点
public:
void init(int a,int b) //初始化并查集
{
start=a,n=b;
for(int i=start;i<=n;i++){
pre[i]=i;
rank[i]=1;
}
}
int findPre(int x) //寻找某个节点的上级
{
if(pre[x]==x) return x;
return pre[x]=findPre(pre[x]);
}
bool isSame(int x,int y) //判断某两个节点是否连通
{ return findPre(x)==findPre(y); }
bool unite(int x,int y) //判断两个节是否连通，如果未连通则将其连通并返回真，否则返回假
{
x=findPre(x);
y=findPre(y);
if(x==y) return false;
if(rank[x] > rank[y]) pre[y]=x;
else{
if(rank[x]==rank[y]) rank[y]++;
pre[x]=y;
}
return true;
}
bool isOne() //判断整个无向图中的所有节点是否连通
{
int temp=findPre(start);
for(int i=start+1;i<=n;i++)
if(findPre(i)!=temp) return false;
return true;
}
};
class Kruskal{ //Kruskal算法：求解无向连通图中的最小生成树
private:
int n,m; //n,m分别表示输入的点和边的个数
static const int MAX=N;
Edge e[MAX]; //存放录入的无向连通图的所有边
vector<Edge> s; //存放最小生成树里的所有边
UnionFindSet u; //并查集：抽象实现Graphnew，并完成节点间的连接工作以及判断整个图是否连通
public:
Kruskal(int a,int b) //构造函数：参数a,b分别表示录入的无向连通图的节点数和边数
{
n=a,m=b;
int x,y,length;
for(int i=0;i<m;i++){ //录入边信息
cin>>x>>y>>length;
e[i]=Edge(x,y,length);
}
sort(e,e+m,cmp); //对录入的边进行排序
u.init(1,n); //初始化并查集u
}
void run() //执行函数：求解录入的无向连通图的最小生成树
{
for(int i=0;i<m;i++){ //按序遍历所有边
if(u.unite(e[i].x,e[i].y)) s.push_back(e[i]); //如果当前边能够被接受，则说明这条边属于最小生成树
if(u.isOne()) break; //一旦Graphnew的连通分支数为1，则说明求出了最小生成树
}
}
void print() //打印函数
{
cout<<"构成最小生成树的边为："<<endl;
int edgeSum=0;
for(int i=0;i<s.size();i++){
cout<<"边 <"<<s[i].x<<","<<s[i].y<<"> = "<<s[i].length<<endl;
edgeSum+=s[i].length;
}
cout<<"最小生成树的权值为："<<edgeSum<<endl;
}
};
int main()
{
int n,m;
cin>>n>>m; //输入无向连通图的节点数和边数
Kruskal kruskal(n,m); //构建Kruskal类
kruskal.run(); //开始计算其最小生成树
kruskal.print(); //打印结果
return 0;
}
这里我们同样在程序运行时，输入以下内容（即图一）：
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
运行后得到的效果如下：
转载：https://blog.csdn.net/the_ZED/article/details/105938353