数据结构学习小记5之最小生成树
连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边，这样的连通子图称为连通图的生成树。
在一个连通图的所有生成树中，各边的代价之和（即各边的权值最小）的那棵生成树称为该连通网的最小生成树。
普里姆(Prim)算法
(1)构造过程
假设N=(V,E)是连通网，TE是N上最小生成树中边的集合
U={u0}(u0∈V),TE={}（U中是在生成过程中将点纳入的集合）
在所有u∈U,v∈V-U的边（u,v）∈E中找一条权值最小的边(u0,v0)并入集合TE,同时v0并入U中
重复2，直至U=V为止。
此时TE中必有n-1条边，则T=（V,TE）为N的最小生成树的例子。可以看出Prim算法逐步增加U中的顶点，可称为"加点法"。
（2）算法实现
struct
{
VetTexType adjvex;//最小边在U中的那个顶点
ArcType lowcost;//最小边上的权值
}closedge[MVNum];
//这是辅助数组，用来记录从顶点集U到V-U的权值的边
具体过程
void MiniSpanTree_Prim(AMGraph G,VerTexType u)
{//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
k=LocateVex(G,u);//k为顶点u的下标
for(j=0;j<G.vexnum;++j)//对每一个顶点vj,初始化closedge[j]
if(j!=k) closedge[j]={u,G.arcs[k][j]};
closedge[k].lowcost=0; //lowcost存储最小边上的权值
for(i=1;i<G.vexnum;++i)
{//选择其余n-1个顶点，生成n-1条边（n=G.vexnum）
k=Min(closedge);
//求出T的下一个结点：第k个顶点，closedge[k]中存有当前最小边
u0=closedge[k].adjvex; //u0为最小边的一个顶点，u0∈U
v0=G.vexs[k]; //v0为最小边的另一个顶点，v0∈V-U
cout<<u0<<v0;//输出当前的最小边(u0,v0)
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j]<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j]};//选出最小的权值得到最小边将新顶点并入U
}
}
【算法分析】
算法的时间复杂度为O(n^2),与网中的边数无关，因此适用于求稠密图网的最小生成树。
克鲁斯卡尔算法
（1）构造过程
假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列
初始状态是只有n个顶点而无边的非连通图T=（V,{}）,图中每个顶点自成一个连通分量
在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上（即不形成回路），则将此边加入到T中，否则舍去此边而选择下一条权值最小的边。
重复2，直至T中所有顶点都在同一连通分量上为止
（2）算法实现
struct
{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost;//边上的权值
}Edge[arcnum];
//以上为结构体数组Edge：存储边的信息
int Vexset[MVNum];
//该数组用于标记各个顶点所属的连通分量
具体过程
void MiniSpanTree_Kruskal(AMGraph G)
{
Sort(Edge);//权值从小到大排序
for(i=0;i<G.vexnum;++i)
Vexset[i]=i;
for(i=0;i<G.arcnum;++i)
{
v1=LocateVex(G,Edge[i].Head);
v2=LocateVex(G,Edge[i].Tail);
vs1= Vexset[v1];//获取边的始点所在的连通分量vs1
vs2= Vexset[v2];//获取边的终点所在的连通分量vs2
if(vs1!=vs2)
{
cout<<Edge[i].Head<<Edge[i].Tail;//输出此边
for(j=0;j<G.vexnum;++j)//合并vs1和vs2两个分量，两个集合统一编号
if(Vexset[j]==vs2)
Vexset[j]=vs1;
}
}
【算法分析】
该算法的时间复杂度为O(elog2e),与网中的边数有关，与普里姆算法相比，克鲁斯卡尔算法更适合求稀疏图的最小生成树。
