边的权值之和最小的生成树Minimum-Spanning-Tree
假设G=(V, E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边(u, v)的最小生成树。
任意一个生成树T，添加一条边e则会产生回路，删除该回路中的任一条边，则又恢复为生成树，若e小于删除的那条边，则得到一个更小的生成树。
在建立的时候，所添加的边都为避免生成回路的可添加的边中最小的，则最后生成的生成树是不可改进的。任意边换进去得到的回路中，换进去的那条边一定是最大的。
采用贪心算法
GENERIC_MST(G)
{
T=NULL;
while T未形成一棵生成树;
do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
T=TU(u, v);
}
Prim
初始化：向空树T=(VT, ET)中添加图G=(V, E)的任一顶点u0，使VT={u0}，ET=空集
循环（重复下列操作至VT=V)：从G中选择满足{(u, v)|u∈VT，v∈V-VT}且具有最小权值的边(u, v)，把v加入VT，这条边加入ET
时间复杂度O(|V|^2)不依赖于|E|，因此适用于求解边稠密的图的最小生成树。
struct{
VertexType adjvex; //与哪个VT中的点相连
VRType lowcost; //权值
}closeedge[MAX_SIZE];
//数组下标与图的点数组下标一致
void MiniSpanTree(MGraph G, VertexType u)
{
k=LocateVex(G, u);
for(j=0;j<G.vexnum;++j)
if(j!=k)
closeedge[j]={u, G.arcs[k][j];
closeedge[k].lowcost=0;
for(i=0;i<G.vexnum;++i)
{
k=minimum(closeedge); //下一个要加入生成树的点
printf(closeedge[k].adjvex, G.vexs[k]); //输出生成树上一条边
closeedge[k].lowcost=0; //将k加入VT
for(j=0;j<G.vexnum;++j) //修改其它顶点的最小边
if(G.arcs[k][j]<closeedge[j].lowcost)
closeedge[j]={G.vexs[k], G.arcs[k][j]}
}
Kruskal
Prim是选顶点，Kruskal是选边
初始化：VT=V，ET=空集，每个顶点构成一棵独立的树
循环（重复下列操作至T是一棵树）：按G的边的权值递增顺序依次从E-ET中选择一条边，若这条边加入T后不构成回路，则加入ET，知道ET中有n-1条边。
用类似于并查集的算法，通常采用堆来存放边的集合，每次选择最小权值的边只需O(log|E|)
时间复杂度O(|E|log|E|)，适用于边稀疏而顶点较多的图。
Typedef struct{
int vi, vj, w;
}edgeset[MAX_SIZE_E];
int set[MAX_SIZE_V];
int FindSet(int set[], int v)
{
i=v;
while(set[i]>0) i=set[i];
return i;
}
void krusal(edgeset get, int n, int e)
{
//get为权按从小到大到顺序排序的边集数组
for(i=0;i<=n;++i) set[i]=0;
i=1; //get中的下标
j=1; //生成树中的边数
while(j<n)//一共要获得n-1条边
{
v=FindSet(set, get[i].vi);
w=FindSet(set, get[i].vj);
if(v!=w){
//vi,vj不在同一集合，不会构成回路
cout<<get[i].vi<<","<<get[i].vj<<endl;
set[v]=w;
++j;
}
++i;
}
}
