精选优质文档-倾情为你奉上算法分析与设计实验报告第 次实验实验名称贪心法求最小生成树实验目的通过上机实验，掌握贪心算法的思想，利用Prim算法求解最小生成树并实现。使用贪心法设计连通带权图最小生成树。实验原理(1) 一无向连通带权图，用visited数组标记该顶点是否被访问，用map数组表示边的权值，low存储最小权值,result计算最终的权值之和即最小花费；(2) 首先置S=1，选取满足：i属于S，k属于V-S，且mapik最小的边，将顶点k添加到S中去，直到S=V为止。(3) 设置数组closesti表示与顶点i之间权值最小的顶点，便于输出最小生成树。实验步骤(1) 首先，用二维数组记录点和权值;(2) 选取一个点作为起始点，选择与它邻近的权值最小的点，用low数组更新最小权值。比较得到最小权值，用visited标记为1；无法到达的点用maxInt表示。(3) 再在延伸的点继续找与它邻近的两者权值最小的点，将顶点依次加入S集合中，更新low和closest的值，累加更新最小权
