贪心算法实验最小生成树.docx
- 文档编号:12535065
- 上传时间:2023-06-06
- 格式:DOCX
- 页数:8
- 大小:17.34KB
贪心算法实验最小生成树.docx
《贪心算法实验最小生成树.docx》由会员分享,可在线阅读,更多相关《贪心算法实验最小生成树.docx(8页珍藏版)》请在冰点文库上搜索。
贪心算法实验最小生成树
算法分析与设计实验报告
第一次附加实验
姓名
学号
班级
时间
12.12上午
地点
工训楼309
实验名称
贪心算法实验(最小生成树)
实验目的
通过上机实验,要求掌握贪心算法的思想,利用prim算法求解最小生成树并
实现。
实验原理
设G=(V,E)是连通带权图,V={1,2,…,n}G。
的最小生成树的Prim算法
的基本思想是:
首先置S={1},然后,只要S是V的真子集,就作如下的贪心选择:
选取满足条件iS,jV-S,且c[i][j]最小的边,将顶点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到的所有边恰好构成G
的一棵最小生成树。
实验步骤
(1)用邻接矩阵表示无向图,并进行初始化,冋时选择源点放在集合s中;
(2)选取候选集中距离最短的顶点,把其加入终点集合中;
(3)以该顶点为新考虑的中间顶点,修改候选集中个顶点距离,若经过该点
后,各点到达源点距离比原来距离短,则修改距离;
(4)重复以上2、3步,直到所有候选集中都被加入到终点集中。
关键代码
template
//参数为结点个数n,和无向带权图中各结点之间的距离c[][N+1]
voidPrim(intn,Typec[][N+1])
{
Typelowcost[N+1];//记录c[j][closest]的最小权值intclosest[N+1];//V-S中点j在中的最临接顶点
bools[N+1];//标记各结点是否已经放入集合s中
s[1]=true;
//初始化s[i],lowcost[i],closest[i]
for(inti=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for(inti=1;i { Typemin=inf; intj=1; for(intk=2;k<=n;k++)//找出V-S中是lowcost最小的顶点 j { if((lowcost[k] s[k]))//如果k的lowcost比 min小并且k结点没有被访问 min=lowcost[k];//更新min的值 j=k; } } coutvvjvv''< s[j]=true;//将j添加到集合s中 for(intk=2;k<=n;k++) { if((c[j][k] s[k]))//s集合放进j后更新 各结点的lowcost的值 { lowcost[k]=c[j][k]; closest[k]=j; } } } } 输入较小的有向带权图结果: 测试结果 ±1F弭1(5斂心舜法\胪1ltg\inexo 连通带权图的姮畛厂 99習76±599999999 £^999G999939999 15? ? ? ? S64 5599992 99999699999999£ 9沖9汕沾426些汕甘 山”算法最/J、生成侖扌选边次序如~F: 21 63 46 n* ThetimeisM.UU2 F青按任意犍雄绫…・ 实验分析 再求最小生成树的实验中,有两种算法: 一种是Prim算法,一种是Kruskal算法。 在两种算法中,我们可以比较Prim算法,是通过集合S中的点来更新另一个集合的点距这个已经生成的树的最短距离,而Kruskal算法是每次都选 择最短的边加入到生成树集合中,其实两种算法其思想是不同的,所以两种算法的时间复杂度也是不同的,Prim算法的时间复杂度是0(nA2),而Kruskal算法的时间复杂度是0(nlogn),相比来讲,在时间上Kruskal更好一点。 实验心得 最小生成树在之前的数据结构中也是学过的,可是当时学的时候,也许是 不够努力,学的模模糊糊的,也没有将Prim算法和Kruskal算法搞清楚,只 是能简单的利用知识做题,却不能很清楚地讲明白这两种算法的原理差别,更 别说是编程设计了,那就根本想都不要想,完全不知所措,在之前的数据结构 中,很多涉及到图的实现,尤其那些代码实在是晦涩难懂,搞得我实在不想学 习,后来在算法课上学到的东西就有点不同了,也许是经过时间的打磨,感觉 到现在的代码没有那么难懂了,也终于弄明白了两者的区别,感觉好多了。 实验得分 助教签名 附录: 完整代码(贪心法) //贪心算法最小生成树prim算法 #include #inelude #inelude #inelude #include usingnamespacestd; #defineinf9999;//定义无限大的值 constintN=6; template voidPrim(intn,Typec[][N+1]); intmain() { intc[N+1][N+1]; cout<<"连通带权图的矩阵为: "< for(inti=1;i<=N;i++)//输入邻接矩阵 for(intj=1;j<=N;j++) { cin>>c[i][j]; } } cout<<"Prim算法最小生成树选边次序如下: "< clock_tstart,end,over;//计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock(); Prim(N,c);//调用Prim算法函数 end=clock(); //显示 printf("Thetimeis%6.3f",(double)(end-start-over)/CLK_TCK);运行时间 cout< system("pause"); return0; } template //参数为结点个数n,和无向带权图中各结点之间的距离c[][N+1] voidPrim(intn,Typec[][N+1]) { Typelowcost[N+1];//记录c[j][closest]的最小权值 intclosest[N+1];//V-S中点j在s中的最临接顶点 bools[N+1];//标记各结点是否已经放入S集合| s[1]=true; //初始化s[i],lowcost[i],closest[i] for(inti=2;i<=n;i++) { lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; } for(inti=1;i { Typemin=inf; intj=1; for(intk=2;k<=n;k++)//找出V-S中是lowcost最小的顶点j { if((lowcost[k] s[k]))//如果k的lowcost比min小并且k结 点没有被访问 { min=lowcost[k];//更新min的值 j=k; } } coutvvjvv''< s[j]=true;//将j添加到s中 for(intk=2;k<=n;k++) { if((c[j][k] s[k]))//s集合放进j后更新各结点的 lowcost的值 { lowcost[k]=c[j][k]; closest[k]=j; } } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法 实验 最小 生成