最小耗费生成树Prim算法实验报告.doc

学 生 实 验 报 告学 院： 软件与通信工程学院 课程名称： 算法设计与分析 专业班级： 软件工程142班 姓 名： 周 平 学 号： 0143987 学生实验报告学生姓名周平学号0143987同组人：无实验项目最小耗费生成树Prim算法必修 选修 演示性实验 验证性实验 操作性实验 综合性实验实验地点W101实验仪器台号K03指导教师尹爱华实验日期及节次5-234一、实验综述实现贪心法的下列六个算法之一：1、可切割背包问题2、单源点最短路径求解算法Dijkstra算法3、Dijkstra算法的改进版4、最小耗费生成树Kruskal算法5、最小耗费生成树Prim算法6、最小耗费生成树Prim算法的改进版要求与说明：1、各人独立完成，2、实验报告要求有：算法说明与描述、代码、数据集合（各算法1 要求达到百、千级）。3、实验报告要有2-3个截图，包括导入数据、重要中间过程、最后结果等；4、额外完成所实现的算法，每完成一个加 1 分；5、程序要求用 C 语言完成，每个实验报告的代码都会被测试，对运行环境有特别要求的需要专门说明，否则，程序测试不通过责任自负；6、实验报告都有步骤分，但是，程序测试结果与实验报告结果不相符的，将被加重扣分；7、严禁抄袭代码重复度超过90%者视作抄袭，抄袭者以 0 分记，可以对评审提出质疑。疑。2、实验仪器、设备或软件1、个人电脑2、Microsoft Visual Studio 2015二、实验过程（实验步骤、记录、数据、分析）实验代码如下:#include #include #define MAX 100#define MAXCOST 0x7fffffffint graphMAXMAX;int Prim(int graphMAX, int n)/* lowcosti记录以i为终点的边的最小权值，当lowcosti=0时表示终点i加入生成树 */int lowcostMAX;/* msti记录对应lowcosti的起点，当msti=0时表示起点i加入生成树 */int mstMAX;int i, j, min, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化 */for (i = 2; i = n; i+)/* 最短距离初始化为其他节点到1号节点的距离 */lowcosti = graph1i;/* 标记所有节点的起点皆为默认的1号节点 */msti = 1;/* 标记1号节点加入生成树 */mst1 = 0;/* n个节点至少需要n-1条边构成最小生成树 */for (i = 2; i = n; i+)min = MAXCOST;minid = 0;/* 找满足条件的最小权值边的节点minid */for (j = 2; j = n; j+)/* 边权值较小且不在生成树中 */if (lowcostj min & lowcostj != 0)min = lowcostj;minid = j;/* 输出生成树边的信息:起点，终点，权值 */printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min);/* 累加权值 */sum += min;/* 标记节点minid加入生成树 */lowcostminid = 0;/* 更新当前节点minid到其他节点的权值 */for (j = 2; j = n; j+)/* 发现更小的权值 */if (graphminidj lowcostj)/* 更新权值信息 */lowcostj = graphminidj;/* 更新最小权值边的起点 */mstj = minid;/* 返回最小权值和 */return sum;int main()printf(请输入点数和边数：);int i, j, k, m, n;int x, y, cost;char chx, chy;scanf(%d%d, &m, &n);/* 读取节点和边的数目 */getchar();printf(请输入边的信息：);/* 初始化图，所有节点间距离为无穷大 */for (i = 1; i = m; i+)for (j = 1; j = m; j+)graphij = MAXCOST;/* 读取边信息 */for (k = 0; k n; k+)scanf(%c %c %d, &chx, &chy, &cost);getchar();i = chx - A + 1;j = chy - A + 1;graphij = cost;graphji = cost;/* 求解最小生成树 */cost = Prim(graph, m);/* 输出最小权值和 */printf(Total:%dn, cost);/system(pause);return 0;代码说明：1、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。2、lowcosti记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树，因此lowcosti = graph1i，即最小边权值就是各节点到1号节点的边权值。3、msti记录的是lowcosti对应的起点，这样有起点，有终点，即可唯一确定一条边了。初始化时msti = 1，即每条边都是从1号节点出发。编写程序:对于如下一个带权无向图，给出节点个数以及所有边权值，用Prim算法求最小生成树。三、结论1、实验结果输入数据:7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11输出:A - D : 5D - F : 6A - B : 7B - E : 7E - C : 5E - G : 9Total:39实验结果如图：2、分析讨论Prim算法的基本思想如下：首先从V中任取一个顶点(假定取v1),将生成树T置为仅有一个结点v1的树，即U=v1;然后只要U是V的真子集，就在所有那些一个端点在T中，另一个端点在T外的边中，找一条最短（即权值最小 )的边。假定符合条件的最短边为(vi,vj),则把该条边和其不在T中的顶