图的遍历及最小生成树实验报告(共10页).doc

《图的遍历及最小生成树实验报告(共10页).doc》由会员分享，可在线阅读，更多相关《图的遍历及最小生成树实验报告(共10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点最后建立此图的最小生成树，并将对应的边及权值写入文件graph_prim.txt中。六、详细设计实验内容(原理、操作步骤、程序代码)#include#include#include#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大顶点个数int visitedMAX_VERTEX_NUM;typedef struct ArcCellint adj;int *info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTE

3、X_NUM;typedef struct closechar adjvex;int lowcost;closedgeMAX_VERTEX_NUM;typedef structchar vexsMAX_VERTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数closedge cld;MGraph;typedef struct QNode char data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front1; QueuePtr rear

4、;LinkQueue;void (*VisitFunc)(MGraph G,int v);void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v);void DFS(MGraph G,int v);void InitQueue(LinkQueue &Q) Q.front1=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front1) exit(0); Q.front1-next=NULL;void EnQueue(LinkQueue &Q,char e) QueuePtr p=(QueuePtr

5、)malloc(sizeof(QNode); if(!p) exit(0); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p;char DeQueue(LinkQueue &Q) if(Q.front1=Q.rear) exit(0); QueuePtr p=Q.front1-next; char e=p-data; Q.front1-next=p-next; if(Q.rear=p) Q.rear=Q.front1; free(p); return e;int QueueEmpty(LinkQueue Q) if(Q.front1=Q.rear)

6、 return 1; return 0;int LocateVex(MGraph &G,char v1) int i=0; while(!(G.vexsi=v1) i+; return i;char GetVex(MGraph G,int i) char u; u=G.vexsi; return u;int minimum(MGraph G,closedge cld) int mini=1000,s1; for(int i=0;icldi.lowcost) mini=cldi.lowcost; s1=i; return s1;void CreateUDN(MGraph &G) int IncI

7、nfo; printf(请分别输入顶点数/弧数/以及弧所含信息:); scanf(%d %d %d,&G.vexnum,&G.arcnum,&IncInfo); getchar(); for(int i=0;iG.vexnum;i+) /构造顶点向量 printf(请输入顶点:); scanf(%c,&G.vexsi); getchar(); for(int i=0;iG.vexnum;i+) /初始化邻接矩阵 for(int j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcsij.info=NULL; for(int k=0;kG.arcnum;k

8、+) char v1,v2; int w,i,j; printf(输入一条边依附的顶点及权值:); /构造邻接矩阵 scanf(%c %c %d,&v1,&v2,&w); /输入一条边依附的顶点及权值 i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcsij.adj=w; if(IncInfo) *G.arcsij.info=IncInfo; G.arcsji=G.arcsij; getchar(); /深度优先遍历void Visit(MGraph G,int v) printf(%c,G.vexsv);void DFSTraverse(MGraph G,

9、void (* Visit)(MGraph G,int v) VisitFunc=Visit; for(int v=0;vG.vexnum;v+) visitedv=0; for(int v=0;vG.vexnum;v+) if(!visitedv) DFS(G,v); void DFS(MGraph G,int v) visitedv=1; VisitFunc(G,v); for(int j=0;jG.vexnum;j+) if(!visitedj&G.arcsvj.adj!=INFINITY) DFS(G,j);void BFSTraverse(MGraph G,void(*Visit)(

10、MGraph G,int v) LinkQueue Q; for(int v=0;vG.vexnum;v+) visitedv=0; InitQueue(Q); for(int v=0;vG.vexnum;v+) if(!visitedv) visitedv=1; Visit(G,v); EnQueue(Q,G.vexsv); while(!QueueEmpty(Q) DeQueue(Q); for(int j=0;jG.vexnum;j+) if(!visitedj&G.arcsvj.adj!=INFINITY) visitedj=1; Visit(G,j); EnQueue(Q,G.vex

11、sj); void MiniSpanTree_PRIM(MGraph G,char u) FILE *IN; if(IN=fopen(graph_prim.txt,w+)=NULL) printf(file open error!); exit(1); int k=LocateVex(G,u); for(int j=0;jG.vexnum;j+) if(j!=k) G.cldj.adjvex=u; G.cldj.lowcost=G.arcskj.adj; G.cldk.lowcost=0; for(int i=1;iG.vexnum;i+) k=minimum(G,G.cld); printf

12、(%c%c,G.cldk.adjvex,G.vexsk); int m=LocateVex(G,G.cldk.adjvex); printf(%dn,G.arcsmk.adj); fprintf(IN,%c,%c,%d,G.cldk.adjvex,G.vexsk,G.arcsmk.adj); fputs(n,IN); G.cldk.lowcost=0; for(int j=0;jG.vexnum;j+) if(G.arcskj.adjG.cldj.lowcost) G.cldj.adjvex=G.vexsk; G.cldj.lowcost=G.arcskj.adj; fclose(IN);vo

13、id menu() printf(1.生成无向网Gn); printf(2.最小生成树n); printf(3.深度遍历n); printf(4.广度遍历n); printf(0.退出n);int main(void) MGraph G; int m; do menu(); printf(输入你想要进行的操作的序号:); scanf(%d,&m); getchar(); switch(m) case 1: CreateUDN(G); break; case 2: char u; u=GetVex(G,0); MiniSpanTree_PRIM(G,u); break; case 3: DFSTraverse(G,Visit); break; case 4: BFSTraverse(G,Visit); break; case 0: break; default: break; while(m);七、测试结果(截图)主界面八、实验心得 1拼写错误节应该避免2尽量用通俗易懂的标示符定义函数、变量3变量应该先定义再使用4应该从使用者的角度考虑，做出简洁的主界面5编好一个函数时应该加注释方便以后阅读时好理解专心-专注-专业