2020-03-03

问题

最小生成树是一副连通加权无向图中一棵权值最小的生成树。它具有如下特点：1、包含所有n个顶点2、有n-1条边3、最小的权值总和

解析

Prim算法，也称“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

具体步骤如下：

[if !supportLists]（1）[endif]选择任意顶点，把图中顶点分为两个不同的顶点集S（生成树的顶点集）和V-S。

[if !supportLists]（2）[endif]在两个不同顶点集组成的边中选择权值最小的边加入到生成树中。

[if !supportLists]（3）[endif]将该边的另一点加入到S中，从V-S中删除。

[if !supportLists]（4）[endif]重复（2）（3）步骤，直到V-S为空集。

Kruskal算法，可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

具体步骤如下：

（1）把图中顶点看成n个不同的顶点集，每个顶点集都含有1个顶点。

（2）在两个不同顶点集组成的边中选择权值最小的边加入到生成树中。

（3）直到图中所有顶点都在同一个顶点集为止。

设计

//Prim算法

for (int e = 1; e <= vexCounts -1; e++)  //n-1条边时退出

    {

int k = Minmum(closedge);  //选择最小代价边

cout << vextex[closedge[k].data] << "--" << vextex[k] << endl;//加入到最小生成树

closedge[k].lowestcost = 0; //代价置为0

for (int i = 0; i < vexCounts;i++)  //更新v中顶点最小代价边信息

        {

            if ( adjMat[k][i] < closedge[i].lowestcost)

            {

                closedge[i].data = k;

                closedge[i].lowestcost = adjMat[k][i];

            }

        }

}

//Kruskal算法

for (unsigned int i = 0; i < vertexArc.size(); i++)//依次从小到大取最小代价边

    {

        VertexData u = vertexArc[i].u;  

        VertexData v = vertexArc[i].v;

if (FindTree(u, v, Tree))//检查此边的两个顶点是否在一颗树内

        {

cout << vextex[u] << "---" << vextex[v] << endl;//把此边加入到最小生成树中

        }   

    }

源码

https://github.com/snocc2953/-2019-2020-2/blob/master/ex1.cpp