最小生成树
如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。
1. 普利姆（Prim）算法
假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。
- U={u0}(u0∈V)， TE={ }。
- 在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。
重复2，直至U=V为止。
此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树。
算法步骤：
为实现这个算法需附设一个辅助数组closedge,以记录从U到V-U具有最小权值的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，他包含2个域：lowcost和adjvex,其中lowcost存储最小边上的权值，adjvex存储最小边在U中的那个顶点。显然closedge[i-1].lowcost = Min{cost(u,vi)|u∈U},其中cost(u,v)表示赋予边（u,v）的权。
struct
{
VerTextType adjvex;//最小边在U中的那个顶点
ArcType lowcost;//最小边上的权值
}closedge[MVNum];
- 首先将初始顶点u加入U中，对于其余的每一个顶点vj,将closedeg[j]均初始化为到u的边信息。
- 循环n-1次，做如下处理：
- 从各组边closedeg中选出最小边closedge[k],输出此边。
- 将k加入U中。
- 更新剩余的每组最小边信息closedeg[j],对于V-U中的边，新增加一条从k到j的边，如果新边的权值比closedeg[j].lowcost小，则将closedge[j].lowcost更新为新边的权值。
void MiniSpanTree_Prim(AMGraph G,VerTexType u)
{//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树，输出T的各条边
k = LocateVex(G,u);//k为顶点u的下标
for(j=0 ;j<G.vexnum;++j)//对于V-U的每一个顶点vj,初始化closedge[j]
if (j!=k) closedge[j] = {u,G.arcs[k][j]};//{adjvex,lowcost}
closedeg[k].lowcost = 0;//初始，U={u}
for(i=1;i<G.vexnum;++i)
{//选择其余n-1个顶点，生成n-1条边（n = G.vexnum）
k= Min(colsedge);
//求出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;//第k个顶点并入U集
for(j=0;j<G.vexnum;++i)
if(G.arcs[k][j] < closedge[j].lowcost)//新顶点并入U后重新选择最小边
colsedge[j] = {G.vexs[k],G.arcs[k][j]};
}
}
2. 克鲁斯卡算法
假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列。
- 初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。
- 在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。
重复2，直至T中所有顶点都在同一个连通分量上为止。
算法的实现要引入以下辅助的数据结构。
- 结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值。
struct
{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost; // 边上的权值
}Edge[arcnum]
- Vexset[i]:标识各个顶点所属的连通分量。对每个顶点vi∈V ,在辅助数组存在一个相应元素Vexset[i]表示该顶点所在连通分量。初始时Vexset[i],表示各个顶点自成一个连通分量。
int Vexset[Mvnum];
算法步骤：
- 将数组Edge中的元素按权值从小到大排序。
- 依次查看数组Edge中的边，循环执行以下操作：
- 依次从排序好的数组Edge中选出一条边（U1,U2）
- 在Vexset中分别查找v1和v2 所在的连通分量vs1 和vs2，并进行判断：
*如果vs1 和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1 和vs2两个连通分量。
*如果vs1 和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。
void MiniSpanTree_Kruskal(MGraph G)
{//无向网以邻接矩阵形式存储，构造G的最小数T，输出T的各条边
sort(Edge);//将数组Edge中的元素按权值从小到大排序
for(i=0;i<G.vexnum;i++)//辅助数组，表示各个顶点自成一个连通分量
Vexset[i] = i;
for(i=0;i<G.arcnum;i++)//依次查看数组Edge中的边
{
v1 = LocateVex(G,Edge[i].Head);//v1为边的始点Head的下标
v2 = LocateVex(G,Edge[i].Tail);//v2为边的终点Tail的下标
vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1
vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量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;//集合编号为vs2的都改为vs1
}
}
}
