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

实验三最小生成树问题班级：计科1101班学号：0909101605姓名：杜茂鹏2013年5月23日一、实验目的掌握图的存储表示和以及图的最小生成树算法。二、实验内容1.实现图的存储，并且读入图的内容。2.利用普里姆算法求网络的最小生成树。3.实现构造生成树过程中的连通分量抽象数据类型。4.以文本形式输出对应图的最小生成树各条边及权值。三、实验要求1．在上机前写出全部源程序；2．能在机器上正确运行程序；3．用户界面友好。四、概要设计、首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件Graph.txt中。然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点最后建立此图的最小生成树，并将对应的边及权值写入文件graph_prim.txt中。六、详细设计实验内容(原理、操作步骤、程序代码)#includestdio.h#includestdlib.h#includelimits.h#defineINFINITYINT_MAX//最大值#defineMAX_VERTEX_NUM20//最大顶点个数intvisited[MAX_VERTEX_NUM];typedefstructArcCell{intadj;int*info;//该弧相关信息的指针}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*next;}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.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.rear==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(inti=0;iG.vexnum;i++){if(cld[i].lowcost!=0&&minicld[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;iG.vexnum;i++){//构造顶点向量printf(请输入顶点:);scanf(%c,&G.vexs[i]);getchar();}for(inti=0;iG.vexnum;i++)//初始化邻接矩阵for(intj=0;jG.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}for(intk=0;kG.arcnum;k++){charv1,v2;intw,i,j;printf(输入一条边依附的顶点及权值:);//构造邻接矩阵scanf(%c%c%d,&v1,&v2,&w);//输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=w;if(IncInfo)*G.arcs[i][j].info=IncInfo;G.arcs[j][i]=G.arcs[i][j];getchar();}}//深度优先遍历voidVisit(MGraphG,intv){printf(%c,G.vexs[v]);}voidDFSTraverse(MGraphG,void(*Visit)(MGraphG,intv)){VisitFunc=Visit;for(intv=0;vG.vexnum;v++)visited[v]=0;for(intv=0;vG.vexnum;v++)if(!visited[v]){DFS(G,v);}}voidDFS(MGraphG,intv){visited[v]=1;VisitFunc(G,v);for(intj=0;jG.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY)DFS(G,j);}voidBFSTraverse(MGraphG,void(*Visit)(MGraphG,intv)){LinkQueueQ;for(intv=0;vG.vexnum;v++)visited[v]=0;InitQueue(Q);for(intv=0;vG.vexnum;v++)if(!visited[v]){visited[v]=1;Visit(G,v);EnQueue(Q,G.vexs[v]);while(!QueueEmpty(Q)){DeQueue(Q);for(intj=0;jG.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY){visited[j]=1;Visit(G,j);EnQueue(Q,G.vexs[j]);}}}}voidMiniSpanTree_PRIM(MGraphG,charu){FILE*IN;if((IN=fopen(graph_prim.txt,w+))==NULL){printf(fileopenerror!);exit(1);}intk=LocateVex(G,u);for(intj=0;jG.vexnum;j++)if(j!=k){G.cld[j].adjvex=u;G.cld[j].lowcost=G.arcs[k][j].adj;}G.cld[k].lowcost=0;for(inti=1;iG.vexnum;i++){k=minimum(G,G.cld);printf(%c%c,G.cld[k].adjvex,G.vexs[k]);intm=LocateVex(G,G.cld[k].adjvex);printf(%d\n,G.arcs[m][k].adj);fprintf(IN,%c,%c,%d,G.cld[k].adjvex,G.vexs[k],G.arcs[m][k].adj);fputs(\n,IN);G.cld[k].lowcost=0;for(intj=0;jG.vexnum;j++)if(G.arcs[k][j].adjG.cld[j].lowcost){G.cld[j].adjvex=G.vexs[k];G.cld[j].lowcost=G.arcs[k][j].adj;}}fclose(IN);}voidmenu(){printf(1.生成无向网G\n);printf(2.最小生成树\n);printf(3.深度遍历\n);printf(4.广度遍历\n);printf(0.退出\n);}intmain(void){MGraphG;intm;do{menu();printf(输入你想要进行的操作的序号:);scanf(%d,&m);getchar();switch(m){case1:CreateUDN(G);break;case2:charu;u=GetVex(G,0);MiniSpanTree_PRIM(G,u);break;case3:DFSTraverse(G,Visit);break;case4:BFSTraverse(G,Visit);break;case0:break;default:break;}}while(m);}七、测试结果(截图)主界面八、实验心得1拼写错误节应该避免2尽量用通俗易懂的标示符定义函数、变量3变量应该先定义再使用4应该从使用者的角度考虑，做出简洁的主界面5编好一个函数时应该加注释方便以后阅读时好理解