实验五图操作实现实验日期：2017年4月27日实验目的及要求1.熟练掌握图的邻接矩阵和邻接
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的存储方式；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
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;ivn;i++){/*二维数组初始化*/for(j=0;jvn;j++){g->arcs[i][j]=0;}}for(v=0;vvn;v++){/*确定数据*/g->vex[v]=a;a++;}printf("输入结构:\n");/*确定边*/for(v=0;ven;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;jvn;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;ivn;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):");/*BFS输出*/bfs(&g,v);printf("\n");}5．程序执行时屏幕上的输入输出内容A图结构：BCDE实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）
浙公网安备 33021202002483