最小生成树

如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。

1. 普利姆（Prim）算法

假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。

1. U={u0}(u0∈V)， TE={ }。
2. 在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。

3. 重复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];

1. 首先将初始顶点u加入U中，对于其余的每一个顶点vj,将closedeg[j]均初始化为到u的边信息。
2. 循环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中的边按权值从小到大的顺序排列。

1. 初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。
2. 在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。

3. 重复2，直至T中所有顶点都在同一个连通分量上为止。

   
   
   

   算法的实现要引入以下辅助的数据结构。

1. 结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值。

struct
{
      VerTexType Head;//边的始点
      VerTexType Tail;//边的终点
       ArcType  lowcost;  //    边上的权值
}Edge[arcnum]

2. Vexset[i]:标识各个顶点所属的连通分量。对每个顶点vi∈V ,在辅助数组存在一个相应元素Vexset[i]表示该顶点所在连通分量。初始时Vexset[i],表示各个顶点自成一个连通分量。

int Vexset[Mvnum];

算法步骤：

1. 将数组Edge中的元素按权值从小到大排序。
2. 依次查看数组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
              }
      }
}