实验五图操作实现.doc

《实验五图操作实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五图操作实现实验日期：2017年4月27日实验目的及要求1.熟练掌握图的邻接矩阵和邻接表的存储方式；2.实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D...，而非键盘输入），分别用dfs（深度优先搜索）和bfs(广度优先搜索)遍历，输出图中顶点信息并验证。邻接矩阵图类型定义：#defineMAX40typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;访问标记数组定义：intvi

2、sited[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,in

3、tv)/*访问v号顶点*/（3）voiddfs(MGraph*g,intv)/*邻接矩阵存储的图的深度优先搜索*/（4）voidbfs(MGraph*g,intv)/*邻接矩阵存储的图的广度优先搜索*/3．回答下列问题（1）现有定义：MGraph*g，并且g指针指向的无向图已创建完成，请写出该图遍历前需初始化visited数组的C程序语句。for(i=0;i

4、r(i=0;ivn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}4．自定义函数库文件Queue.h与sy15.cpp源程序清单（含必要的注释）Queue.h:#includetypedefintdatatype;/*队列元素为图的顶点下标,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*顺序存储的循环队列类型*/voidInitQueue(SeqQueue*Q);/*初始化队列*/voidEnQueue(SeqQueue*Q,int

5、v);/*入队*/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(S

6、eqQueue*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#include"Queue.h"intvisited[MAX];/*值为0时对应顶点未被访问，值为

7、1时对应顶点已被访问*/typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;voidcreateGraph(MGraph*g);/*建邻接矩阵存储的无向图*/voidvisit(MGraph*g,intv);/*访问v号顶点*/voiddfs(MGraph*g,intv);/*邻接矩阵存储的