实验五-图操作实现

实验五图操作实现实验日期：2017年4月27日实验目的及要求1.熟练掌握图的邻接矩阵和邻接表的存储方式；2.实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D...，而非键盘输入），分别用dfs（深度优先搜索）和bfs(广度优先搜索)遍历，输出图中顶点信息并验证。邻接矩阵图类型定义：#defineMAX40typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;访问标记数组定义：intvisited[MAX];/*值为0时对应顶点未被访问，值为1时对应顶点已被访问*/顺序存储的循环队列类型定义：typedefintdatatype;/*队列元素为图的顶点下标,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*顺序存储的循环队列类型*/任务1．自定义函数库文件Queue.h，完成队列的相关操作。2．创建一个程序文件sy15.cpp，自定义相应函数完成以下操作：（1）voidcreateGraph(MGraph*g)/*建邻接矩阵存储的无向图*/（2）voidvisit(MGraph*g,intv)/*访问v号顶点*/（3）voiddfs(MGraph*g,intv)/*邻接矩阵存储的图的深度优先搜索*/（4）voidbfs(MGraph*g,intv)/*邻接矩阵存储的图的广度优先搜索*/3．回答下列问题（1）现有定义：MGraph*g，并且g指针指向的无向图已创建完成，请写出该图遍历前需初始化visited数组的C程序语句。for(i=0;ig.vn;i++){/*标记数组初始化*/visited[i]=0;}（2）定义函数intcount(MGraph*g)统计非连通图的连同分量个数。（说明：借助遍历算法实现）intcount(MGraph*g){inti,m=0;for(i=0;ig-vn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}4．自定义函数库文件Queue.h与sy15.cpp源程序清单（含必要的注释）Queue.h:#includestdio.htypedefintdatatype;/*队列元素为图的顶点下标,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*顺序存储的循环队列类型*/voidInitQueue(SeqQueue*Q);/*初始化队列*/voidEnQueue(SeqQueue*Q,intv);/*入队*/datatypeDeQueue(SeqQueue*Q);/*出队*/intEmptyQueue(SeqQueue*Q);/*判队空*/intFullQueue(SeqQueue*Q);/*判队满*/voidInitQueue(SeqQueue*Q){Q-front=Q-rear=0;}voidEnQueue(SeqQueue*Q,intv){if(FullQueue(Q)){printf(队列已满!);/*判队满*/return;}Q-rear=(Q-rear+1)%MAX;/*入队*/Q-data[Q-rear]=v;}datatypeDeQueue(SeqQueue*Q){if(EmptyQueue(Q)){printf(队列为空!);/*判队空*/return-1;}Q-front=(Q-front+1)%MAX;/*出队*/returnQ-data[Q-front];}intEmptyQueue(SeqQueue*Q){returnQ-front==Q-rear;}intFullQueue(SeqQueue*Q){return(Q-rear+1)%MAX==Q-front;}sy5.cpp:#defineMAX40#includeQueue.hintvisited[MAX];/*值为0时对应顶点未被访问，值为1时对应顶点已被访问*/typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;voidcreateGraph(MGraph*g);/*建邻接矩阵存储的无向图*/voidvisit(MGraph*g,intv);/*访问v号顶点*/voiddfs(MGraph*g,intv);/*邻接矩阵存储的图的深度优先搜索*/voidbfs(MGraph*g,intv);/*邻接矩阵存储的图的广度优先搜索*/voidcreateGraph(MGraph*g){inti,j,v;chara='A';printf(输入顶点数:);/*输入顶点数和边数*/scanf(%d,&g-vn);printf(输入边数:);scanf(%d,&g-en);for(i=0;ig-vn;i++){/*二维数组初始化*/for(j=0;jg-vn;j++){g-arcs[i][j]=0;}}for(v=0;vg-vn;v++){/*确定数据*/g-vex[v]=a;a++;}printf(输入结构:\n);/*确定边*/for(v=0;vg-en;v++){scanf(%d%d,&i,&j);g-arcs[i][j]=1;g-arcs[j][i]=1;}}voidvisit(MGraph*g,intv){printf(%c,g-vex[v]);}voiddfs(MGraph*g,intv){intj;visit(g,v);/*输出数据*/visited[v]=1;/*标记已访问*/for(j=0;jg-vn;j++){if(g-arcs[v][j]==1&&visited[j]==0){dfs(g,j);/*递归*/}}}voidbfs(MGraph*g,intv){inti,w;SeqQueueQ;InitQueue(&Q);/*队列初始化*/EnQueue(&Q,v);/*入队*/visited[v]=1;/*标记已访问*/while(!EmptyQueue(&Q)){w=DeQueue(&Q);/*出队*/visit(g,w);/*输出数据*/for(i=0;ig-vn;i++){if(g-arcs[w][i]==1&&visited[i]==0){EnQueue(&Q,i);/*入队*/visited[i]=1;/*标记已访问*/}}}}voidmain(){MGraphg;inti,v;createGraph(&g);/*建图*/for(i=0;ig.vn;i++){/*标记数组初始化*/visited[i]=0;}printf(开始顶点:);/*输入遍历开始顶点*/scanf(%d,&v);printf(输出(dfs):);/*DFS输出*/dfs(&g,v);printf(\n);for(i=0;ig.vn;i++){/*标记数组初始化*/visited[i]=0;}printf(输出(bfs):);/*BFS输出*/bfs(&g,v);printf(\n);}5．程序执行时屏幕上的输入输出内容A图结构：BCDE实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）