最小生成树算法实验报告

1、最小生成树算法问题的说明设g=(v，e )为无方向连通带的权重图，设e中的各边(v，w )的权重为c(v，w )。 如果g的一个子图g 是包含g的所有顶点的书，则将g 称为g的生成树。 生成树的各边的权重的总和称为该生成树的消耗，g的所有生成树中消耗最少的生成树称为g的最小生成树。 给出无向连通带权重图，构建最小生成树。设计思想用prim算法求最小生成树，prim算法是用贪婪策略设置修正的算法。 设g=(v，e )为连通带权图，v= 1，2，2，n。 构成g的一个最小生成树的prim算法的基本思想是首先放置u=1，接下来如果u是v的真实子集，那么它满足条件i-u，jv-u并一贯进行c(i，j

2、)，直到该过程变成u=v。 在这个过程中被选择的所有边恰好构成g的一个最小生成树。时间的复杂性prim算法的pascal语言描述如下程序主机(c :阵列. n，1.n )。华尔街低成本：阵列。整合器关闭：阵列。i、j、k、min、整数；联苯胺(1) for i :=2待办事项(2) begin初始化，此时u仅包含顶点1 。低成本，低成本，低成本。(4)关闭 i :=1。(5)结束(6) for i :=2待办事项(7) begin 顶点分别在v-u和u中寻找权重最小的边。最小3360=低成本；(9) j:=i(10 ) for k :=2待办事项(十一)低成本。cout(0gei.weight

3、0) 。计算(ijw；检查(n，i，j )；中断(k=e-1 )。中国语：中国语。 k；while(1)；数字=e=k；cout 邻接矩阵：n ；for(i=0； i=n |j0 | j=n )cout 输入有错误，请重新输入！ ；激活恢复；cinij； 是是/从图的邻接矩阵生成图的边集阵列voidadjmlist :3360变更代码集(rcw ge ，int n，int e )只设想无向图的情况int i，j，k=0；for(i=0； i=0； j- )国际货币基金组织包括号包括号包含图形. cpp void主机()。rcw rcw= 0，1，50 ， 1，0，50 ， 0，2，60 ， 2

4、，0，60 ，一、三、六十五、三、一、六十五、一、四、四十、一、四十、二、三、五十二、三、二、五二、六、四五、六、二、四五、三、四、五十、四、三、五十、是三、五、三十、五、三、三十、三、六、四十二、六、三、四十二、五、七十、一。氮、钾； /定义图的点数和边数等cout 输入图的点数n=； cinn；cout 输入图的边数k=； 连接；静态rcw ae (30 )、be30 )； /定义边集数组adj列表a (ae、n、k )；创建矩阵(n、k、rcw )；cout输出边缘集阵列的每个边缘：n；变换代码集(ae，n，k )；a .输出端口(ae，k )；按cout 升序排列的图的边缘集阵列：n ；a .存储代码集(ae，k )；a .输出端口(ae，k )；普里姆(be，n )；cout最小生成树的边集数组：n；a .输出端口(be，k )；cin.get ()； cin.get ()； 是实验数据主程序中的直接结构图的边缘表如下所示0、1、50、1、0、50、0、2、60、2、0、60、一、三、六十五、三、一、六十五、一、四、四十、一、四十、二、三、五十二、三、二、五二、六、四五