Prim算法求最小生成树

《Prim算法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第次实验实验名称贪心法求最小生成树实验目的通过上机实验，掌握贪心算法的思想，利用Prim算法求解最小生成树并实现。使用贪心法设计连通带权图最小生成树。实验原理(1)一无向连通带权图，用visited[]数组标记该顶点是否被访问，用map[][]数组表示边的权值，low[]存储最小权值,result计算最终的权值之和即最小花费；(2)首先置S=1，选取满足：i属于S，k属于V-S，且map[i][k]最小的边，将顶点k添加到S中去，直到S=V为止。(3)设置数组closest[i]表示与顶点i之间权值最小的顶点，便于输出最小生成树。实验步骤(1)

2、首先，用二维数组记录点和权值;(2)选取一个点作为起始点，选择与它邻近的权值最小的点，用low数组更新最小权值。比较得到最小权值，用visited[]标记为1；无法到达的点用maxInt表示。(3)再在延伸的点继续找与它邻近的两者权值最小的点，将顶点依次加入S集合中，更新low[]和closest[]的值，累加更新最小权值之和result.(4)所有点连通后，即得到最小生成树。关键代码intprim(){inti;intmin=MaxInt,result=0;memset(visited,0,sizeof(visited));visited[1]=1;//从某点开始

3、，分别标记和记录该点for(i=2;i<=n;i++){low[i]=map[1][i];//给low数组赋值closest[i]=1;visited[i]=0;}for(i=1;ilow[j]){min=low[j];k=j;cout<

4、tj=2;j<=n;j++)//更新权值if(visited[j]==0&&low[j]>map[k][j]){low[j]=map[k][j];closest[j]=k;}}returnresult;}测试结果最小生成树N=4:最小生成树N=5:最小生成树N=6:实验心得通过本次实验明白了最小生成树贪心算法的设计思路，掌握了prim算法选边的原理，我将课本上的算法加以改进，同时输出最小生成树和最小花费，完善了代码。在课本上了解了另外一种经典算法Kruskal算法，它按权的递增顺序查看边的序列可以看做一个优先队列，优先级为边的权，也了解了并查集这种抽象的数据类型。P

5、rim算法十分经典，在设计通信网络中常用于解决城市之间通信线路所需费用的问题，感觉十分经济实用。附录：完整代码#include#include#include#include#include#defineMaxInt0x3f3f3f3f#defineN110usingnamespacestd;//创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问intmap[N][N],low[N],closest[N],visited[N];

6、intn;intprim(){inti;intmin=MaxInt,result=0;memset(visited,0,sizeof(visited));visited[1]=1;//从某点开始，分别标记和记录该点for(i=2;i<=n;i++){low[i]=map[1][i];//给low数组赋值closest[i]=1;visited[i]=0;}for(i=1;ilow[j]){m

7、in=low[j];k=j;cout<map[k][j]){low[j]=map[k][j];closest[j]=k;}}returnresult;}intmain(){inti,p=0;doublek=0.0;clock_tstart,end,over;start=clock();end=clock();over=e