最小生成树性质克鲁斯卡尔（Kruskal）算法Kruskal算法过程#include<iostream>#include<algorithm>usingnamespacestd;structEdge{inta,b;//边的两个顶点的编号intd;//边的权值}edge[11111];intn,m,s;//n为无向图的顶点个数,m为边的条数,s用来存放最小生成树的总权值introot[111];//存储父节点boolcmp(Edgea,Edgeb){returna.d<b.d;}intfind(inta)//寻找父节点{if(root[a]==a)returna;returnroot[a]=find(root[a]);}boolUnion(inta,intb,intd)//合并{if(a==b)return0;//a==b说明边的两个顶点一属于同一颗树，所以不需要合并，直接返回root[a]=b;//将a的父节点更新为b，从而将树a，b合并成一棵树s+=d;//将边的权值加到s当中return1;}voidkruskal(){for(inti=0;i<n;i++)//初始化，将各顶点的父节点标记为本身root[i]=i;sort(edge,edge+m,cmp);//将所有边根据边的权值从小到大排列s=0;for(i=0;i<m;i++)//遍历所有的边{if(Union(find(edge[i].a),find(edge[i].b),edge[i].d))n--;//当合并成功，森林的树就少一棵}//当遍历完所有的边时,如果n!=1,说明该无向图不是连通图,不存在最小生成树}MST性质MST性质基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。关键:是如何找到连接U和V-U的最短边。U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}Prim算法Prim算法Prim算法Prim算法Prim算法设置一个数组shortEdge[n]来表示候选最短边集，数组元素包括两个域：adjvex和lowcost。adjvex：表示最短边的邻接点（属于集合U）下标；lowcost：表示最短边的权值，lowcost=0表示该顶点已加入最小生成树中。i数组1.将顶点0加入集合U中；2.初始化辅助数组shortEdge，分别为lowcost和adjvex赋值；3.重复执行下列操作n-1次3.1在shortEdge中选取最短边，取其对应的下标k；3.2输出边(k,shortEdge[k].adjvex)和对应的权值；3.3将顶点k加入集合U中；3.4调整数组shortEdge；Prim算法流程Prim算法过程//数组lowcost[n]：用来保存非生成树中各顶点与生成树中顶点最短边的权值；//数组vis[n]：用来表示顶点v是否已加入最小生成树中。intpos=0;sum=0;//sum用来存放最小生成树的总权值for(i=0;i<n;i++)//{//map[0][i]：选取编号为0的顶点加入最小生成树中lowcost[i]=map[0][i];//将其余各顶点到编号0顶点的权值存储到lowcost当中vis[i]=0;//起始状态，所有点都未加入到最小生成树中}vis[0]=1;//编号为0的顶点加入最小生成树中for(i=1;i<n;i++)//n-1次，n为顶点个数{Min=999999;for(j=0;j<n;j++){if(Min>lowcost[j]&&!vis[j])//寻找满足一个顶点未加入生成树,另一个顶点已加入生成树的最小边{Min=lowcost[j];pos=j;}}sum+=Min;vis[pos]=1;//将顶点pos加入生成树for(j=0;j<n;j++)//更新由顶点pos到其他未加入生成树的顶点边的权值{if(lowcost[j]>map[pos][j]&&!vis[j])lowcost[j]=map[pos][j];}}