徐州工程学院数据结构最小生成树实验文档

1、实验九 图的最小生成树算法的实现实验预备知识：1 .理解图最小生成树的意义和相应算法。2. 掌握带权图的存储结构。、实验目的1. 使学生熟悉最小生成树的算法实现。2. 掌握带权图的存储结构和处理方法。二、实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或 Windows操作系统 +Turbo C;三、实验要求1. 能够独立完成带权图的存储和最小生成树的生成 四、实验内容1. 在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本 次实验的所有程序和数据都要求存储到本文件夹中。2. 现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请

2、用合适的存储结构将下图存储到计算机中方便进行处理。3. 现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用 普里姆算法和克鲁斯卡尔算法实现本图的最小生成树#in clude <stdio.h>#in clude <stdlib.h>#defi neINF 50typ edef struct ArcNodeint adjvex;struct ArcNode *n extarc; int weight;ArcNode;/该弧所指向的顶点位置/下一个临接点/弧的权重/表结点/顶点信息/指向下一个结点typ edef struct VNode char data;

3、ArcNode *firstarc;VNode,AdjList6;typ edef struct AdjList LH; int vexnum; int arcnum;Grap h;创建头结点数组/图的点的个数/图的边的个数typ edef struct char n extvex; int lowcost; int know;/辅助数组结构体Auxiliary_array;void main (void)void buildtu (Gra ph*);void prin tgra ph(Gra ph*);void p rim( Graph *G, char u);char u;Graph UD

4、G;Graph *G = & UDG;buildtu(G);printgraph(G);/ 打印图printf(”请输入起始顶点：n"); while(getchar()!='n');u = getchar();prim(G ,u);void buildtu (Gra ph *G) / 建图int search(Gra ph *G,char a);int i,n 1, n2,w; char a,b; ArcNode *p, *q;printf(”请输入顶点个数和边的条数：n”)；scan f("%d %d",&G->vex n

5、um,&G->arc num);printf(”请输入顶点信息n");for (i = 0; i < G->vex num; +i)while (getchar()!='n');sca nf("%c", &G->LHi.data); G->LHi.firstarc = NULL;printf(”请输入有关系的结点和该边的权重:n");for(i=0;i<G->arc nu m;+i)while (getchar()!='n');sca nf("%c %c

6、%d"，& a,&b,&w);n 1=search(G,a);n2=search(G,b);p=G->LH n1.firstarc;if(p = NULL)p=G->LH n1.firstarc=(ArcNode *) malloc (sizeof(ArcNode); elsewhile( p-> nextarc !=NULL )p=p->n extarc;p=p->n extarc=(ArcNode *) malloc (sizeof(ArcNode);q=G->LH n2.firstarc;if(q = NULL)q=G

7、->LH n2.firstarc=(ArcNode *) malloc (sizeof(ArcNode);elsewhile( q-> nextarc !=NULL )q=q->n extarc;q=q->n extarc=(ArcNode *) malloc (sizeof(ArcNode); p->adjvex=n2;p->weight=w;p->n extarc=NULL;q->adjvex=n1; q->weight=w; q->n extarc=NULL;int search (Graph *G,char a) II确定顶点

8、a在头结点数组中的位置 int i;for(i=0;i<G->vex nu m;+i)if(G->LHi.data=a) return i;void printgraph(Graph *G)/ 打印图int i;ArcNode *p;for (i=0 ; i < G->vex num; +i)p=G->LHi.firstarc;prin tf("data:%c t",G->LHi.data);while( p!=NULL)prin tf("firstarc->adjvex=%d", p->adjvex

9、); p=p->n extarc;prin tf("n");void prim( Graph *G, char u)/用prim算法实现最小生成树 int search (Gra ph *G,char a);int mi ni mize(Gra ph *G, Auxiliary_array);void prin ttable(Auxiliary_array);Auxiliary_array A6;/ 创建辅助数组int i,j,seat;int locatio n;ArcNode *p ;for (i = 0; i < G->vex num; +i) Ai

10、 .n extvex = '0'Ai.k now = 0;Ai.lowcost = INF;location = search(G ,u);/确定u元素在头结点数组中的位置 for (p=G->LHlocati on .firstarc ; p != NULL; p=p->n extarc )i = p->adjvex;Ai. nextvex = G->LHlocati on .data;Ai .lo wcost = p->weight;Ai.k now = 0;Alocati on .k now = 1;Alocati on .lowcost =

11、 0;Alocati on . nextvex = 'O'for(j=0;j<G->vex nu m-1;+j)seat = mini mize( G,A );prin tf("select min: %dn", seat);Aseat.k now = 1;p=G->LHseat.firstarc;for (p; p != NULL; p=p->n extarc)i=p->adjvex;if(Ai.k now = 0 && p->weight < Ai.lowcost)Ai. nextvex = G-

12、>LHseat.data;Ai .lo wcost = p->weight;printtable(A); /打印辅助数组中的信息for (j = 0; j < G->vex num; +j)if (j != locati on)prin tf("%c<->%c rr,Aj. nextvex,G->LHj.data);int mi nimize(Gra ph *G, Auxiliary_array A)/取出辅助数组中权值最小的顶点所在的位置int i,p lace ,num;num = INF;for (i = 0; i < G->

13、;vex num; +i)if(Ai.k now = 0 && num >= Ai.lowcost) num = Ai.lowcost;p lace = i;retur n p lace; void prin ttable(Auxiliary_array A) / 打印辅助数组int i;for (i = 0; i < 6; i+) prin tf("modifier:%clowcost:%d known:%dn",Ai. nextvex,Ai.lowcost,Ai.k no w);实验总结：通过该实验，我深刻明白到了自己对循环的能力不足，书写代

14、码的逻辑性也不够 强，相信在以后的学习中能加强这方面的学习，争取在以后的学习中解决这两个方面 的问题。请福j m点牛我利7占的索；聂: 13请辎入顶点信息abdf请输入有关系的结点和该边的权重;bcdf c d £1firstarc->adjuex= 1 f irttar(;->adjuex=2f irsterc->acl ju«x=3 firstarc->adjuex=Ofirstarc->adjuex=firstarc->aci juex=2 firstarc->adjuex=Ofiritarc->adju«x=

15、>lfirstare->adju#x=5firstarc->adjuex=1datadatadataf ir®tarc->aclkiex=3 dat A data ：e data：ffirstflrc->fldjuex=Ofirstart->adjuex=5firstarc->aci jux=2 firs t arc->adj uex=1firetarc*>adjvex=2fir&terc-adjyex=5 firstarc->adjuex=2fir3tarc->adjuexi3firstarc->aci ju*x=4 请输入起始顶点！3w«lectselectselectselect001 电 Ctmin： min： min：min： mini itiodifier：O