最小生成树

雨点打透心脏的1/2处 2022-03-18 12:28 270阅读 0赞

问题提出：  
要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。  
问题分析：  
答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。  
结论：  
希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 —— 最小代价生成树。  
构造最小生成树的算法很多，其中多数算法都利用了一种称之为 MST 的性质。  
MST 性质：设 N = (V, E) 是一个连通网，U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u, v) 的最小生成树。

（1）普里姆 (Prim) 算法

算法思想：  
①设 N=(V, E)是连通网，TE是N上最小生成树中边的集合。  
②初始令 U=\{u\_0\}, (u\_0∈V), TE=\{ \}。  
③在所有u∈U，u∈U-V的边(u,v)∈E中，找一条代价最小的边(u\_0,v\_0 )。  
④将(u\_0,v\_0 )并入集合TE，同时v\_0并入U。  
⑤重复上述操作直至U = V为止，则 T=(V,TE)为N的最小生成树。

代码实现：

void MiniSpanTree_PRIM(MGraph G,VertexType u)
        //用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
        //记录从顶点集U到V-U的代价最小的边的辅助数组定义；
        //closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
    {
        int k, j, i;
        k = LocateVex(G,u);
        for (j = 0; j < G.vexnum; ++j)    //辅助数组的初始化
            if(j != k)
            {
                closedge[j].adjvex = u;
                closedge[j].lowcost = G.arcs[k][j].adj;    
    //获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
            }
        closedge[k].lowcost = 0;        
    //初始，U = {u};  
        PrintClosedge(closedge,G.vexnum);
        for (i = 1; i < G.vexnum; ++i)    \
    //选择其余G.vexnum-1个顶点，因此i从1开始循环
        {
            k = minimum(G.vexnum,closedge);        
    //求出最小生成树的下一个结点：第k顶点
            PrintMiniTree_PRIM(G, closedge, k);     //输出生成树的边
            closedge[k].lowcost = 0;                //第k顶点并入U集
            PrintClosedge(closedge,G.vexnum);
            for(j = 0;j < G.vexnum; ++j)
            {                                           
                if(G.arcs[k][j].adj < closedge[j].lowcost)    
    //比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
                {
                    closedge[j].adjvex = G.vexs[k];//替换closedge[j]
                    closedge[j].lowcost = G.arcs[k][j].adj;
                    PrintClosedge(closedge,G.vexnum);
                }
            }
        }
    }

（2）克鲁斯卡尔 (Kruskal) 算法

算法思想：  
①设连通网 N = (V, E )，令最小生成树初始状态为只有n个顶点而无边的非连通图，T=(V, \{ \})，每个顶点自成一个连通分量。  
②在 E 中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。  
③依此类推，直至 T 中所有顶点都在同一连通分量上为止。  
  
最小生成树可能不惟一！