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

《数据结构 实验8 最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告-4-1、实验目的（1)复习图的存储方法和图的遍历方法；（2)进一步掌握图的非线性特点、递归特点和动态特性；（3)掌握最小生成树的求解算法。2、实验内容（1)用Prim算法求最小生成树；（2)输入网的二维矩阵，输出最小生成树；3、实验要求（1)分析算法思想，利用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，并求最小生成树。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步

2、骤与源程序⑴实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要首先使用prim的函数将矩阵初始化，然后输出无向图的邻接矩阵，再求最小生成树的求解算法，最后，编写主函数，串接程序，并调试程序，得出实验结果。⑵源代码#include#defineinf9999#definemax40voidprim(intg[][max],intn)//prim的函数{intlowcost[max],closest[max];inti,j,k,min;for(i=2;i<=n;i++)/

3、/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;《算法设计与分析》实验报告-4-k=0;for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]

4、,%d)%dt",closest[k],k,min);lowcost[k]=0;//顶点k加入Ufor(j=2;j<=n;j++)//修改由顶点k到其他顶点边的权值if(g[k][j]

5、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);《算法设计与分析》实验报告-4-g[v1][v2]=weight;g[v2][v1]=weight;}return(n);}voidprg(intg[][max],intn)//输出无向图的邻接矩阵{inti,j;for(i=0;i<=n;i++

6、)printf("%dt",i);for(i=1;i<=n;i++){printf("%dt",i);for(j=1;j<=n;j++)printf((g[i][j]==inf)?"t":"%dt",g[i][j]);}printf("");}voidmain(){intg[max][max],n;n=adjg(g);printf("输入无向图的邻接矩阵:");prg(g,n);printf("最小生成树的构造:");prim(g,n);}1、测试数据与实验结果（可以抓图粘贴）《算法设计与分

7、析》实验报告-4-1、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。这次的实验我们要做的是图的存储方法和图的遍历方法，要求我们掌握的是非线性特点，递归特点和动态特征，最小生成树的求解等。首先将初始化矩阵，全部元素设为无穷大，使用的是prim的函数，输出无向图的邻接矩阵。在做这次实验之前先参考了一个例子，在结合书本的要求编写程序，在调试程序的过程中，遇到很多问题，但是最终还是得以解决。