Prim算法求最小生成树

算法分析与设计实验报告第 次实验实验名称贪心法求最小生成树实验目的通过上机实验，掌握贪心算法的思想，利用Prim算法求解最小生成树并实现。使用贪心法设计连通带权图最小生成树。实验原理(1) 一无向连通带权图，用visited数组标记该顶点是否被访问，用map数组表示边的权值，low存储最小权值,result计算最终的权值之和即最小花费；(2) 首先置S=1，选取满足：i属于S，k属于V-S，且mapik最小的边，将顶点k添加到S中去，直到S=V为止。(3) 设置数组closesti表示与顶点i之间权值最小的顶点，便于输出最小生成树。实验步骤(1) 首先，用二维数组记录点和权值;(2) 选取一个点作为起始点，选择与它邻近的权值最小的点，用low数组更新最小权值。比较得到最小权值，用visited标记为1；无法到达的点用maxInt表示。(3) 再在延伸的点继续找与它邻近的两者权值最小的点，将顶点依次加入S集合中，更新low和closest的值，累加更新最小权值之和result.(4) 所有点连通后，即得到最小生成树。关键代码int prim() int i;int min=MaxInt,result=0; memset(visited,0,sizeof(visited); visited1=1;/从某点开始，分别标记和记录该点 for(i=2;i=n;i+) lowi=map1i;/给low数组赋值closesti=1;visitedi=0; for(i=1;in;i+)/运行n-1次 /找出最小权值并记录位置 min=MaxInt; int k=1; for(int j=2;jlowj) min=lowj;k=j; coutk与closestk相连endl; result+=min;/最小权值累加visitedk=1;/标记该点for(int j=2;jmapkj) lowj=mapkj; closestj=k; return result;测试结果最小生成树N=4:最小生成树N=5:最小生成树N=6:实验心得通过本次实验明白了最小生成树贪心算法的设计思路，掌握了prim算法选边的原理，我将课本上的算法加以改进，同时输出最小生成树和最小花费，完善了代码。在课本上了解了另外一种经典算法Kruskal算法，它按权的递增顺序查看边的序列可以看做一个优先队列，优先级为边的权，也了解了并查集这种抽象的数据类型。 Prim算法十分经典，在设计通信网络中常用于解决城市之间通信线路所需费用的问题，感觉十分经济实用。附录：完整代码#include#include #include #include #include #define MaxInt 0x3f3f3f3f#define N 110using namespace std;/创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问int mapNN,lowN,closestN,visitedN;int n; int prim() int i;int min=MaxInt,result=0; memset(visited,0,sizeof(visited); visited1=1;/从某点开始，分别标记和记录该点 for(i=2;i=n;i+) lowi=map1i;/给low数组赋值closesti=1;visitedi=0; for(i=1;in;i+)/运行n-1次 /找出最小权值并记录位置 min=MaxInt; int k=1; for(int j=2;jlowj) min=lowj;k=j; coutk与closestk相连endl; result+=min;/最小权值累加visitedk=1;/标记该点for(int j=2;jmapkj) lowj=mapkj; closestj=k; return result;int main()int i,p=0; double k=0.0; clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(); int v,j,ans; cout(以EOF为程序结束符)输入顶点数n:; while(scanf(%d,&n)!=EOF) cout输入n*n的权值矩阵:endl; memset(map,MaxInt,sizeof(map);/所有权值初始化为最大 for(i=1;i=n;i+) for(j=1;jv; mapij=v; ans=prim(); cout最小生成树的权值之和为：ansendl