普里姆与克鲁斯卡尔算法.doc

前言 从学习《数据结构》这门课程开始，已发现的乐趣，在学习的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个的了解Microsoft Visual C++ 6.0所编写的，主要利用贪心算法的思想，以及数组，for语句的循环，if语句的嵌套，运用以上所学知识编写出的prim和kruskal算法求解最小生成树，在输入其边的起始位置，种植位置以及权值后，便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置，终止位置以及权值。 正文 2.1 设计方法和内容 一.软件环境：Microsoft Visual C++ 6.0 二.详细设计思想： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 　　贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 　　贪心算法的基本思路如下： 　　1.建立数学模型来描述问题。 　　2.把求解的问题分成若干个子问题。 　　3.对每一子问题求解，得到子问题的局部最优解。 　　4.把子问题的解局部最优解合成原来解问题的一个解。 　　思想是基于点的贪心，从源点到下一个点的距离最短临接矩阵到下一个点的最短距离kruskal算法的贪心是从源点到下一个点的距离最短。 prim算法的贪心是任意点到生成树的距离最短，也就是边的最小。 tl=t.ct[i].endvex，w=t.s[j][tl]，若wt.ct[i].weight，则令 t.ct[i].weight=w，t.ct[i].fromvex=j。 （6）最后利用for循环键入每条边的起始点，终结点及边上的权值。 2.kruskal算法： （1）定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。 （2）定义一个名为edgeset2的类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。 （3）定义一个名为tree2的类，定义了一个最小生成树边集的数组，用edgeset ge2[e+1]存放网中所有的边，定义一个s2[n+1][n+1]，s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合，若s[i][t]=1。则表示顶点t属于该集合，否则不属于该集合，再定义一个普里姆算法的成员函数kruskal(tree2 t2)。 （4）对kruskal(tree2 t2)函数进行类外定义,定义k并设初值为1用来统计生成树的边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个变量m1,m2用来记录一条边的两个顶点所在集合的序号，如果t2.ge2[d].fromvex==j且t2.s2[i][j]==1，则令m1=i，若t2.ge2[d].endvex==j且t2.s2[i][j]==1则令m2=i，最后判断m1是否等于m2，若不等于则令t2.c2[k]=t2.ge2[d]，k自加，求出一条边后，合并两个集合，另一个集合设置为空。 （6）最后利用for循环键入每条边的起始点，终结点及边上的权值，要求输入的网中的边上的权值必须为从大到小排列，调用kruskal（t）循环输出一条边的起始点，终结点及边上的权值。 2.3设计流程图 图2-2 2.4 设计结论 Prim算法：在图中任取一个顶点k作为开始点，令集合U={ k},集合w=V-U,其中v为图中所有顶点的集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中的所有边中，权值最短的一条边，，并将该边顶点全部加入集合U中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，在重复此过程，直到W为空集为止 Kruskal算法：将无向图的所有边按权值递增顺序排列，依次选定权值数较小的边，但要求后面选取的边不能与前面选区的边构成回路，若构成回路，则放弃该条边，然后再选后面权值较大的边，n个顶点的图中，选取n-1条边即可。 其中两个算法的贪心思想有本质的区别：kruskal算法的贪心是从源点到下一个点的距离最短。prim算法的贪心是任意点到生成树的距离最短，也就是边的最小。 这次，，在实际操作过程中犯的一些错误有意外的收获在具体操作中对这学期所学的的理论知识得到巩固，达到实训的基本目的，在以后的上机中应更加注意发现上机实训的重要作用，特别是对数组和有了深刻的理解。通过实际操作，学会程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。 在此希望多进行这样的实训，培养独立思考问题的能力，提高实际操作水平。#includeiostream.h const int n=6; //网中