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

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

2、计算机中方便进行处理。3现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树.#include #include #defineINF50typedef struct ArcNodeintadjvex;/ 该弧所指向的顶点位置struct ArcNode *nextarc;/ 下一个临接点intweight;/ 弧的权重ArcNode;/ 表结点typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向下一个结点VNode,AdjList6;typedef structAdjLis

3、t LH;/ 创建头结点数组int vexnum;/ 图的点的个数int arcnum;/ 图的边的个数Graph;typedef structchar nextvex;intlowcost;intknow;Auxiliary_array;/ 辅助数组结构体voidmain (void)void buildtu (Graph*);void printgraph(Graph*);void prim( Graph *G, char u);charu;Graph UDG;Graph *G = &UDG;buildtu(G);printgraph(G);/ 打印图printf( 请输入起始顶点：n);

4、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);printf( 请输入顶点信息n);for (i = 0; i vexnum; +i)while (getchar()!=n);scanf(%c,&G-LHi.data);G-LHi.firstarc =

5、NULL;printf( 请输入有关系的结点和该边的权重:n);for(i=0;iarcnum;+i)while (getchar()!=n);scanf(%c %c %d,&a,&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);

6、q=G-LHn2.firstarc;if(q = NULL)q=G-LHn2.firstarc=(ArcNode *) malloc (sizeof(ArcNode);else.while( 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 在头结点数组中的位置 i

7、nt i;for(i=0;ivexnum;+i)if(G-LHi.data=a)return i;void printgraph(Graph *G)/ 打印图int i;ArcNode *p;for (i=0 ; i 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);.void prim( Graph *G, char u)/ 用 prim 算法实现最小生成树int search (Gra

8、ph *G,char a);int minimize(Graph *G, Auxiliary_array);void printtable(Auxiliary_array);Auxiliary_arrayA6;/ 创建辅助数组int i,j,seat;int location;ArcNode*p ;for (i = 0; i vexnum; +i) Ai.nextvex = 0;Ai.know= 0;Ai.lowcost = INF;location = search(G ,u);/ 确定 u 元素在头结点数组中的位置for (p=G-LHlocation.firstarc ; p != NU

9、LL; 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;jvexnum-1;+j)seat = minimize( G,A );printf(select min: %dn, seat);Aseat.know = 1;p=G-LHseat.firstarc;for (p; p != NULL; p=p-nextarc)i=p

10、-adjvex;if(Ai.know = 0 & p-weight LHseat.data;Ai.lowcost = p-weight;.printtable(A); /打印辅助数组中的信息for (j = 0; j 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 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 =