图的遍历及最小生成树实验报告.doc

《图的遍历及最小生成树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三最小生成树问题班级：计科1101班学号：姓名：杜茂鹏2013年5月23日一、实验目的掌握图的存储表示和以及图的最小生成树算法。二、实验内容1.实现图的存储，并且读入图的内容。2.利用普里姆算法求网络的最小生成树。3.实现构造生成树过程中的连通分量抽象数据类型。4.以文本形式输出对应图的最小生成树各条边及权值。三、实验要求1．在上机前写出全部源程序；2．能在机器上正确运行程序；3．用户界面友好。四、概要设计、首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件Graph.txt中。然后利用已经建

2、好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点最后建立此图的最小生成树，并将对应的边及权值写入文件graph_prim.txt中。六、详细设计实验内容(原理、操作步骤、程序代码)#include#include#include#defineINFINITYINT_MAX//最大值#defineMAX_VERTEX_NUM20//最大顶点个数intvisited[MAX_VERTEX_NUM];typedefstructArcCell{intadj;int*info;//该弧相关信

3、息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstructclose{charadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数closedgecld;}MGraph;typedefstructQNode{chardata;structQNode*n

4、ext;}QNode,*QueuePtr;typedefstruct{QueuePtrfront1;QueuePtrrear;}LinkQueue;void(*VisitFunc)(MGraphG,intv);voidDFSTraverse(MGraphG,void(*Visit)(MGraphG,intv));voidDFS(MGraphG,intv);voidInitQueue(LinkQueue&Q){Q.front1=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front1)exit(0);Q.

5、front1->next=NULL;}voidEnQueue(LinkQueue&Q,chare){QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}charDeQueue(LinkQueue&Q){if(Q.front1==Q.rear)exit(0);QueuePtrp=Q.front1->next;chare=p->data;Q.front1->next=p->next;if(Q.rea

6、r==p)Q.rear=Q.front1;free(p);returne;}intQueueEmpty(LinkQueueQ){if(Q.front1==Q.rear)return1;return0;}intLocateVex(MGraph&G,charv1){inti=0;while(!(G.vexs[i]==v1))i++;returni;}charGetVex(MGraphG,inti){charu;u=G.vexs[i];returnu;}intminimum(MGraphG,closedgecld){intmini=1000,s1;for

7、(inti=0;icld[i].lowcost){mini=cld[i].lowcost;s1=i;}}returns1;}voidCreateUDN(MGraph&G){intIncInfo;printf("请分别输入顶点数/弧数/以及弧所含信息:");scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);getchar();for(inti=0;i

8、scanf("%c",&G.vexs[i]);getchar();}for(inti=0;i