数据结构-实验8-最小生成树

《算法设计与分析》实验报告-1-1、实验目的（1)复习图的存储方法和图的遍历方法；（2)进一步掌握图的非线性特点、递归特点和动态特性；（3)掌握最小生成树的求解算法。2、实验内容（1)用Prim算法求最小生成树；（2)输入网的二维矩阵，输出最小生成树；3、实验要求（1)分析算法思想，利用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，并求最小生成树。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要首先使用prim的函数将矩阵初始化，然后输出无向图的邻接矩阵，再求最小生成树的求解算法，最后，编写主函数，串接程序，并调试程序，得出实验结果。⑵源代码#includestdio.h#defineinf9999#definemax40voidprim(intg[][max],intn)//prim的函数{intlowcost[max],closest[max];inti,j,k,min;for(i=2;i=n;i++)//n个顶点，n-1条边{lowcost[i]=g[1][i];//初始化closest[i]=1;//顶点未加入到最小生成树中}lowcost[1]=0;//标志顶点1加入U集合for(i=2;i=n;i++)//形成n-1条边的生成树{min=inf;《算法设计与分析》实验报告-2-k=0;for(j=2;j=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf((%d,%d)%d\t,closest[k],k,min);lowcost[k]=0;//顶点k加入Ufor(j=2;j=n;j++)//修改由顶点k到其他顶点边的权值if(g[k][j]lowcost[j]){lowcost[j]=g[k][j];closest[j]=k;}printf(\n);}}intadjg(intg[][max])//建立无向图{intn,e,i,j,k,v1,v2,weight;printf(输入顶点个数，边的条数：);scanf(%d,%d,&n,&e);for(i=1;i=n;i++)for(j=1;j=n;j++)g[i][j]=inf;//初始化矩阵，全部元素设为无穷大for(k=1;k=e;k++){printf(输入第%d条边的起点，终点，权值:,k);scanf(%d,%d,%d,&v1,&v2,&weight);《算法设计与分析》实验报告-3-g[v1][v2]=weight;g[v2][v1]=weight;}return(n);}voidprg(intg[][max],intn)//输出无向图的邻接矩阵{inti,j;for(i=0;i=n;i++)printf(%d\t,i);for(i=1;i=n;i++){printf(\n%d\t,i);for(j=1;j=n;j++)printf((g[i][j]==inf)?\t:%d\t,g[i][j]);}printf(\n);}voidmain(){intg[max][max],n;n=adjg(g);printf(输入无向图的邻接矩阵:\n);prg(g,n);printf(最小生成树的构造:\n);prim(g,n);}5、测试数据与实验结果（可以抓图粘贴）《算法设计与分析》实验报告-4-6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。这次的实验我们要做的是图的存储方法和图的遍历方法，要求我们掌握的是非线性特点，递归特点和动态特征，最小生成树的求解等。首先将初始化矩阵，全部元素设为无穷大，使用的是prim的函数，输出无向图的邻接矩阵。在做这次实验之前先参考了一个例子，在结合书本的要求编写程序，在调试程序的过程中，遇到很多问题，但是最终还是得以解决。