实验8最小生成树.doc

电子信息学院 实验报告书 课程名： 数据结构 题 目： 最小生成树 实验类别 设计 班 级： BX1008 学 号： 101003150809 姓 名： 胡欢 2011年 11 月 28 日 《最小生成树 》实验报告 -  PAGE 3 - 实验题目 复习图的存储方法和图的遍历方法； 进一步掌握图的非线性特点、递归特点和动态特点； 掌握最小生成树的求解算法。 实验内容 用Prim算法求最小生成树。 输入网的二维矩阵，输出最小生成树。 实验要求 利用C（C++）语言完成算法设计和程序设计。 上机调试通过实验程序，并检验程序运行的正确性。 输入数据，并求最小生成树。 给出具体算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。 实验步骤与源程序  = 1 \* GB2 ⑴ 实验步骤 首先，为了使程序更为通俗易懂，我们在程序开头，初始化形成n-1条边的生成树。 初始化矩阵，编写满足条件的无向图的邻接矩阵。要注意的是，在初始化矩阵的时候全部元素设为无穷大。 根据题意，编写程序。用Prim算法求最小生成树。  = 2 \* GB2 ⑵ 源代码 #include stdio.h #define inf 9999 #define max 40 void prim(int g[][max],int n) // prim的函数 { int lowcost[max],closest[max]; int i,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; 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加入U for(j=2;j=n;j++) // 修改由顶点k到其他顶点边的权值 if(g[k][j]lowcost[j]) { lowcost[j]=g[k][j]; closest[j]=k; } printf(\n); } } int adjg(int g[][max]) // 建立无向图 { int n,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); g[v1][v2]=weight; g[v2][v1]=weight; }