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

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

2、进行处理。3现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树#include <stdio.h>#include <stdlib.h>#define INF 50typedef struct ArcNodeint adjvex; /该弧所指向的顶点位置struct ArcNode *nextarc; /下一个临接点int weight; /弧的权重ArcNode; /表结点typedef structVNodechar data; /顶点信息ArcNode *firstarc; /指向下一个结点VNode,Ad

3、jList6;typedef structAdjList LH; /创建头结点数组int vexnum; /图的点的个数int arcnum; /图的边的个数 Graph;typedef struct char nextvex;int lowcost;int know;Auxiliary_array; /辅助数组结构体void main (void)void buildtu (Graph*);void printgraph(Graph*);void prim( Graph *G, char u); char u;Graph UDG;Graph *G = &UDG;buildtu(G);

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

5、ntf("请输入顶点信息n"); for (i = 0; i < G->vexnum; +i)while (getchar()!='n'); scanf("%c",&G->LHi.data); G->LHi.firstarc = NULL; printf("请输入有关系的结点和该边的权重:n");for(i=0;i<G->arcnum;+i)while (getchar()!='n'); scanf("%c %c %d",&a,&a

6、mp;b,&w);n1=search(G,a);n2=search(G,b); p=G->LHn1.firstarc;if(p = NULL) p=G->LHn1.firstarc=(ArcNode *) malloc (sizeof(ArcNode);elsewhile( p->nextarc !=NULL )p=p->nextarc;p=p->nextarc=(ArcNode *) malloc (sizeof(ArcNode);q=G->LHn2.firstarc;if(q = NULL) q=G->LHn2.firstarc=(ArcN

7、ode *) malloc (sizeof(ArcNode);elsewhile( q->nextarc !=NULL )q=q->nextarc;q=q->nextarc=(ArcNode *) malloc (sizeof(ArcNode);p->adjvex=n2; p->weight=w;p->nextarc=NULL;q->adjvex=n1;q->weight=w;q->nextarc=NULL;int search (Graph *G,char a) /确定顶点a在头结点数组中的位置int i;for(i=0;i<G-&

8、gt;vexnum;+i)if(G->LHi.data=a)return i;void printgraph(Graph *G) /打印图int i; ArcNode *p;for (i=0 ; i < G->vexnum; +i)p=G->LHi.firstarc;printf("data:%c t",G->LHi.data);while(p!=NULL)printf("firstarc->adjvex=%d",p->adjvex);p=p->nextarc;printf("n");v

9、oid prim( Graph *G, char u)/用prim算法实现最小生成树int search (Graph *G,char a);int minimize(Graph *G, Auxiliary_array);void printtable(Auxiliary_array);Auxiliary_array A6; /创建辅助数组int i,j,seat;int location;ArcNode *p ;for (i = 0; i < G->vexnum; +i) Ai.nextvex = '0'Ai.know = 0;Ai.lowcost = INF;

10、location = search(G ,u);/确定u元素在头结点数组中的位置for (p=G->LHlocation.firstarc ; p != NULL; p=p->nextarc )i = p->adjvex;Ai.nextvex = G->LHlocation.data; Ai.lowcost = p->weight;Ai.know = 0;Alocation.know = 1;Alocation.lowcost = 0;Alocation.nextvex = '0' for(j=0;j<G->vexnum-1;+j)se

11、at = minimize( G,A );printf("select min: %dn", seat); Aseat.know = 1;p=G->LHseat.firstarc; for (p; p != NULL; p=p->nextarc) i=p->adjvex; if(Ai.know = 0 && p->weight < Ai.lowcost) Ai.nextvex = G->LHseat.data; Ai.lowcost = p->weight; printtable(A); /打印辅助数组中的信息for

12、 (j = 0; j < G->vexnum; +j)if (j != location)printf("%c<->%cn",Aj.nextvex,G->LHj.data);int minimize(Graph *G, Auxiliary_array A)/取出辅助数组中权值最小的顶点所在的位置int i,place,num;num = INF;for (i = 0; i < G->vexnum; +i)if(Ai.know = 0 && num >= Ai.lowcost)num = Ai.lowcost;place = i;return place;void printtable(Auxiliary_array A) /打印辅助数组int i;for (i = 0; i < 6; i+)