发布时间 : 星期一 文章贪心算法实验（最小生成树）更新完毕开始阅读bc475355b5360b4c2e3f5727a5e9856a561226ac
算法分析与设计实验报告
第 一 次附加实验
姓名 时间 学号 地点 班级 工训楼309 12.12上午 实验名称 贪心算法实验(最小生成树) 实验目的 通过上机实验，要求掌握贪心算法的思想，利用prim算法求解最小生成树并实现。 实验原理 设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 （1）用邻接矩阵表示无向图，并进行初始化，同时选择源点放在集合s中； （2）选取候选集中距离最短的顶点，把其加入终点集合中； （3）以该顶点为新考虑的中间顶点，修改候选集中个顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离； （4）重复以上2、3步，直到所有候选集中都被加入到终点集中。 实验步骤 关键代码 template
} for(int i=1;i 实验分析 再求最小生成树的实验中，有两种算法：一种是Prim算法，一种是Kruskal算法。在两种算法中，我们可以比较Prim算法，是通过集合S中的点来更新另一个集合的点距这个已经生成的树的最短距离，而Kruskal算法是每次都选择最短的边加入到生成树集合中，其实两种算法其思想是不同的，所以两种算法的时间复杂度也是不同的，Prim算法的时间复杂度是O（n^2）,而Kruskal算法的时间复杂度是O（nlogn）,相比来讲，在时间上Kruskal更好一点。 实验心得 最小生成树在之前的数据结构中也是学过的，可是当时学的时候，也许是不够努力，学的模模糊糊的，也没有将Prim算法和Kruskal算法搞清楚，只是能简单的利用知识做题，却不能很清楚地讲明白这两种算法的原理差别，更别说是编程设计了，那就根本想都不要想，完全不知所措，在之前的数据结构中，很多涉及到图的实现，尤其那些代码实在是晦涩难懂，搞得我实在不想学习，后来在算法课上学到的东西就有点不同了，也许是经过时间的打磨，感觉到现在的代码没有那么难懂了，也终于弄明白了两者的区别，感觉好多了。 实验得分 助教签名 附录： 完整代码（贪心法） //贪心算法 最小生成树prim算法 #include using namespace std; #define inf 9999; //定义无限大的值 const int N=6; template int main() { int c[N+1][N+1]; cout<<\连通带权图的矩阵为：\< for(int j=1;j<=N;j++) { 3 / 5 cin>>c[i][j]; } } cout<<\算法最小生成树选边次序如下：\< clock_t start,end,over; //计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock(); Prim(N,c); //调用Prim算法函数 end=clock(); printf(\,(double)(end-start-over)/CLK_TCK); //显示运行时间 cout< system(\); return 0; } template //参数为结点个数n，和无向带权图中各结点之间的距离c[][N+1] void Prim(int n,Type c[][N+1]) { Type lowcost[N+1]; //记录c[j][closest]的最小权值 int closest[N+1]; //V-S中点j在s中的最临接顶点 bool s[N+1]; //标记各结点是否已经放入S集合| s[1]=true; //初始化s[i],lowcost[i],closest[i] for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; } for(int i=1;i Type min=inf; int j=1; for(int k=2;k<=n;k++)//找出V-S中是lowcost最小的顶点j 4 / 5 { if((lowcost[k] min=lowcost[k]; //更新min的值 j=k; } } cout< for(int k=2;k<=n;k++) {