<mark>最小生成树概念及其构建（Prim算法、Kruskal算法）</mark>

基本概念：

由生成树定义可知，无向连通图的生成树不是唯一 的，于是最小生成树的定义诞生，即：无向连通图是一个带权图，她的所有生成树中必有一棵边的权值总和最小的生成树（称为：最小代价生成树，即：最小生成树）

综合来说：Prim算法时间复杂度（O(n^n)）当顶点较少时选择；
Kruskal算法时间复杂度（O(e*loge)）主要耗费在边的排序上，故当边较少时适合选择

一、Prim算法

基本概念：

简单来说：Prim算法就是以点为出发点，通过某一顶点不断寻找相对权值最小的边构造最小生成树，时间复杂度（O(n^2)）

基本思想：

一张图秒懂（转载的。。。）
设置两个集合：
集合U表示用于存放最小生成树的顶点
集合T表示用于存放最小生成树的边

图中u表示已经访问过的顶点、v表示还未访问的顶点

为实现Prim算法，需考虑如何表示最小生成树
书上设置的三个辅助向量（即：数组）：cost[N]、 tree[N]、 vis[N]
其中：
cost[]数组：用来保存最终最小生成树每条边的权值；
tree[]数组：对应于cost[]数组，例如：tree[4]=1;说明当前这条边是(1,4)，即：用顶点v1连通的顶点v4，其权值为cost[4]；
vis[]数组：即标记数组，判断顶点是否被访问（是否进入集合U）；

相关例题：

题目描述：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入：
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

输出：
对每个测试用例，在1行里输出最小的公路总长度。

样例输入：
8
1 2 42
1 3 68
1 4 35
1 5 1
1 6 70
1 7 25
1 8 79
2 3 59
2 4 63
2 5 65
2 6 6
2 7 46
2 8 82
3 4 28
3 5 62
3 6 92
3 7 96
3 8 43
4 5 28
4 6 37
4 7 92
4 8 5
5 6 3
5 7 54
5 8 93
6 7 83
6 8 22
7 8 17
0

样例输出：
82

代码如下：

#include<cstdio> #include<cstring> #include<iostream> #define Max 999999 using namespace std; int mp[110][110]; //邻接矩阵 int cost[110]; //最小生成树每条边的权值 int tree[110]; //与cost[]数组相对应 int vis[110]; //标记数组 int n; //顶点数 /**初始化邻接矩阵*/ void init() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) mp[i][j]=0; else mp[i][j]=Max; //表示两点之间无边 } } } void Prim() {/**由于题目是以1开始编号，于是就从顶点1开始构建*/ //构建的最小生成树存放到tree[]数组中，对应的权值存放到cost[]数组中 memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++) { cost[i]=mp[1][i]; tree[i]=0; } vis[1]=1; tree[1]=-1; cost[1]=0; for(int i=1;i<=n;i++) { int Min=Max+1; int pos; for(int j=1;j<=n;j++) { if(vis[j]==0&&cost[j]<Min) { pos=j; Min=cost[j]; //记忆最小权值的边 } } vis[pos]=1; //表示已经被访问，进入集合U for(int j=1;j<=n;j++) {/**是否用新结点pos连通不在U的顶点*/ if(vis[j]==0&&mp[pos][j]<cost[j]) { cost[j]=mp[pos][j]; tree[j]=pos; } } } } int main() { while(~scanf("%d",&n)) { if(n==0) break; init(); int a,b,value; for(int i=0;i<(n*(n-1)/2);i++) { scanf("%d%d%d",&a,&b,&value); if(mp[a][b]>value) { mp[a][b]=mp[b][a]=value; } } Prim(); int sum=0; /**于是只要把所有边加起来即可*/ for(int i=2;i<=n;i++) sum+=cost[i]; printf("%d\n",sum); } return 0; } 

二、Kruskal算法

基本概念:

简单来说：Kruskal算法正是和Prim完全不同的思路，Kruskal是通过不断寻找最小边，已获得最小生成树

基本思想：
同样一张图秒懂。

主要就是边的排序，于是对边的结构进行些处理方便使用：

typedef struct { int v1; int v2; //两个顶点的序号 int value; //边的权值 }EdgeType; //edges[]数组表示图的所有边的集合，tree[]则表示最小生成树所有边的集合 

为了简化操作，方便选取当前权值最小的边，于是先对edges[]数组进行排序

之后就是需要判断两个顶点是否属于同一集合，于是定义father[]数组

int father[MaxVerNum]; 

例题与Prim算法例题一样，完整代码如下：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MaxEdgNum 110 #define MaxVerNum 5010 using namespace std; typedef struct { int v1; int v2; //两个顶点的序号 int value; //边的权值 }EdgeType; EdgeType edges[MaxEdgNum],tree[MaxVerNum]; //edges[]数组表示图的所有边的集合，tree[]则表示最小生成树所有边的集合 int father[MaxVerNum]; int n; //顶点个数 int e; //边的条数 int Find(int v) { int t; t=v; while(father[t]>=0) t=father[t]; return t; } int num; //记录最小生成树边的条数 void Kruskal() {//城市从1开始编号 /**初始化*/ for(int i=1;i<=n;i++) father[i]=-1; int i=0; num=0; while(i<e-1&&num<n) { int vf1=Find(edges[i].v1); int vf2=Find(edges[i].v2); if(vf1!=vf2) { father[vf2]=vf1; tree[num]=edges[i]; num++; } i++; } } int cmp(EdgeType a,EdgeType b) { if(a.value!=b.value) return a.value<b.value; else if(a.value==b.value&&a.v1!=b.v1) return a.v1<b.v1; else return a.v2<b.v2; } int main() { while(~scanf("%d",&n)) { if(n==0) break; e=n*(n-1)/2; for(int i=0;i<e;i++) { scanf("%d%d%d",&edges[i].v1,&edges[i].v2,&edges[i].value); } /**对edges[]数组按照各边权值由小到大排序*/ sort(edges,edges+e,cmp); /*for(int i=0;i<e;i++) { printf("%d %d %d\n",edges[i].v1,edges[i].v2,edges[i].value); }*/ Kruskal(); int sum=0; for(int i=0;i<num;i++) sum+=tree[i].value; printf("%d\n",sum); } return 0; }