最小生成树 |
您所在的位置：网站首页 › 数据结构prim算法作图软件 › 最小生成树 |
最小生成树
|
目录 适用条件 测试所用图 算法详解 Prim算法代码 全部代码 实验结果 适用条件加权连通图 测试所用图
所用原图及生成过程
其中，(a) 为原图，圆圈里面是节点的名称，边上的数字是边的权值。由实线连接的点就是集合U，即生成树在生成过程中加入的点。由虚线连接的点中不包含在集合U中的就是集合V-U，即待加入到生成树的点。虚线的变化就是在每次有节点加入集合U时，V-U中的点更新到集合U的最小权值，也是贪心算法的精髓之处。 算法详解Prim算法又称为加边法，即每次选择最小权值的边加入到生成树中，然后再更新权值，如此反复，保证每次最优来达到最优解。 所用数据结构 typedef struct closedge { int adjvex; //最小边在集合U（最小边在当前子树顶点集合中的那个顶点的下标） int lowcost; //最小边上的权值 };注：算法中所提到的集合U与集合V-U，可以通过lowcost是否为0进行区分，没必要浪费空间。 初始化 顶点数组下标i012345adjvex000000lowcost0615∞∞集合U0添加第一条边 顶点数组下标i012345adjvex022022lowcost050564集合U0,2可以看到，初始化后，顶点2与集合U(顶点0)之间的距离是最小的。所以，添加顶点2至集合U；接下来进行更新，发现原节点1与集合U（顶点0）之间的距离6>现在节点1与集合U（顶点0、2）之间的距离5，所以进行更新。将adjvex更新为节点1与集合U最小距离时的集合U中顶点，lowcost就是选择的边的权值。 以上的话请读者再仔细阅读一遍，并结合测试所用图来考虑标红的其他部分。下面的表不再赘述。 添加第二条边 顶点数组下标i012345adjvex022525lowcost050260集合U0,2,5添加第三条边 顶点数组下标i012345adjvex022325lowcost050060集合U0,2,5,3添加第四条边 顶点数组下标i012345adjvex012315lowcost000030集合U0,2,3,5,1添加第五条边 顶点数组下标i012345adjvex012345lowcost000000集合U0,2,3,5,1,4 Prim算法代码 //最小生成树-Prim算法 参数：图G void Prim(Graph G) { int v=0;//初始节点 closedge C[MaxVerNum]; int mincost = 0; //记录最小生成树的各边权值之和 //初始化 for (int i = 0; i < G.vexnum; i++) { C[i].adjvex = v; C[i].lowcost = G.Edge[v][i]; } cout |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |