实验五 图操作实现

实验五图操作实现实验五图操作实现实验五图操作实现xxx公司实验五图操作实现文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度实验五图操作实现实验日期：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．自定义函数库文件，完成队列的相关操作。2．创建一个程序文件，自定义相应函数完成以下操作：（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;i<;i++){/*标记数组初始化*/ visited[i]=0;}（2）定义函数intcount(MGraph*g)统计非连通图的连同分量个数。（说明：借助遍历算法实现）intcount(MGraph*g){inti,m=0;for(i=0;i<g->vn;i++)if(visited[i]==0){m++;dfs(g,i);}returnm;}4．自定义函数库文件与源程序清单（含必要的注释）:#include<>typedefintdatatype;/*队列元素为图的顶点下标,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;}:#defineMAX40#include""intvisited[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;i<g->vn;i++){/*二维数组初始化*/ for(j=0;j<g->vn;j++){ g->arcs[i][j]=0; } } for(v=0;v<g->vn;v++){/*确定数据*/ g->vex[v]=a; a++; } printf("输入结构:\n");/*确定边*/ for(v=0;v<g->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;j<g->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;i<g->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;i<;i++){/*标记数组初始化*/ visited[i]=0; } printf("开始顶点:");/*输入遍历开始顶点*/ scanf("%d",&v); printf("输出(dfs):");/*DFS输出*/ dfs(&g,v); printf("\n"); for(i=0;i<;i++){/*标记数组初始化*/ visited[i]=0; } printf("输出(bfs)