最小生成树实验指导书(1)

1、实验1采用普里姆(prim)算法构造网络的最小生成树1、实验目的：深入理解虽小生成树的概念，熟练掌握普里姆(prim)算法的工作过程， 并通过定义合适的数据结构，采用C语言程序实现。2、实验内容：根据模板程序编制普里姆算法的程序，在计算机中进行调试，同时寻找两 个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并把运 行结果与手工生成的结果进行比较，验证程序的正解性。要求从文本文件中读入网络 的邻接矩阵。3、实验原理 prim算法的主要步骤 数据表示 算法实現细节4、实验步骤与实验结果 编写prim算法的C语言程序 输入计算机进行调试 准备两个顶点大于6的网络，把网络的邻接矩

2、阵输入文本文件中，运行程序，记录程 序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果： 画出网络图，写出相应的邻接矩阵 记录程序的运行结果，根据结果画岀最小生成树并写出最小生成树的权值。附录：程序模板# i ncIude /*定义一个结构体，用于记录一条边的始点与终点*/typedef struct ppint p.q； edge;int g100 100. u100, v100, vexnum:edge p100;/用于记录最小生成树的各条边void input()读入图的邻接矩阵(int i. j. temp;FILE *fp;fp=fopen(pp5. t

3、xt, r);fscanf (fp. %d. &vexnum);for (i=1 ： i =vexnwn: i +)Iprintf(n);for (j=1; j=vexniHn： j+)fscanf (fp. %d. &temp):gi j=temp：pr intf (%d , temp):fclose(fp);mainOint i. j. k. m. n. ma. s=0;inputO：/输入数据for (i=1; i=vexnum; i+)集合V中包含了所有顶点vi=1;u1=1：v1=0：/第1个节点加入至集合U中，并从集合V中去掉for (i=1; i=vexnum-1; i+)/最多

4、需 vexnum-1 条边I/以下找连接节点集U至节点集V的最小边ma=1000;/ma存放最小边的权值for (j=1：j=i：j+)集合U中的第j个节点，其编号为uj.每次增加一个, 共有i个for (k=1;k0表示有边*/if (vk !=0&maguj k&gujJ k0)ma=gujk：保存最小边值 m=uj;/最小边的始点编号 n=k：/最小边的终点编号s=s+ma：/ 求和ui+1=n;vn=0：/ffi找到最小边的终点编号从V中去掉，并加入至U中 pi.p=m；pi.q=n;/存最小边的始点编号与终点编号printf (n);for (i=1;i=vexnum-1;i+)pr

5、intf Cn%d %d %d, pi. p. pi. q, gpi.p pi. ql): pr i ntf (nsum=%dnn, s);实验2采用克鲁斯卡尔(kruskal)算法构造网络的最小生成树1、实验目的：深入理解最小生成树的概念，熟练掌握克鲁斯E尔(kruskal)算法的工作 过程，并通过定义合适的数据结构.采用C语言程序实现。2、实验内容：根据模板程序编制克魯斯卡你算法的程序，在计算机中进行调试，同时寻 找两个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。记录运行结果，并 把运行结果与手工生成的结果进行比较，验证程序的正解性。要求从文本文件中读入 网络的邻接矩阵。3、实验原

6、理 克鲁斯卡你算法的主要步骤 数据表示 算法实現细节4、实验步骤与实验结果 编写kruskal算法的C语言程序 输入计算机进行调试 准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程 序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。实验结果： 画出网络图，写出相应的邻接矩阵 记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。1附录：程序模板# i ncIude typedef struct pp/定义最小生成树连的结构int p. q. r ;/顶点1,顶点2,权值 edge：int g100 100. sort100. vexn

7、um：/定义图的邻接矩阵，集合，顶点数 edge p100. temp;void input()读入图的邻接矩阵int i. j. temp;FILE *fp;fp=fopenCpp5. txt, r):fscanf (fp. %d, &vexnum);for (i=1;i=vexnum;i+)Iprintf(n);for (j=1;j=vexnum:j+)fscanf (fp. %d. &temp);gi j=temp;pr intf (%d temp):fclose(fp);ma i n ()(int i. j. k. I. m. sum=0;l=0：input () ；/从文件读入邻接矩

8、阵for (i=1：i=vexnum;i+)初始时，每一顶点属于一个集合 sorti=i;for (i=1; i=vexnum-1; i卄)/把边存入 p 数组for (j=i+1;j0)I+；pl.p=i:pl.q=j：pU. r=gi j:for (i=1;il;i+)/对边按权值进行排序Ik=i;m=pk. r;for (j=i+1：jpjj. r)m=pj. r;k=j；temp=pi；pi=pk；pk=temp;k=1;i=1;whi I e (kvexnwn)Iif(sortpi.p!=sortpi.q)/同一条边的两个节点分别属于两个集合l=sortpi.q：/另一节点的集合号printf Cn%d %d %d. pi. p. pi. q. pi. r)