实验7

学号姓名成绩实验六图的建立和遍历一、实验目的（1）掌握图的邻接矩阵存储结构的表示方法；（2）掌握基于邻接矩阵的图遍历算法的基本思想并能编程实现；二、实验环境PC微机，Windows，VisualC++三、实验内容1、图的邻接矩阵存储结构1）创建测试工程（1）启动VC++6.0，选择菜单“文件”－“新建”；（2）在打开的对话框中选中“工程”选项卡；（3）选择工程类型“Win32ConsoleApplication”；（4）在“工程名称”处输入工程的名字lab6；（5）在“位置”处点击按钮，选择工程存放的目录位置；（6）按“确定”按钮，在出现的向导对话框中，选择“一个空工程”，按“完成”。说明：完成以上步骤后，VC++6.0将在指定的目录位置下创建与工程名同名的目录（如c:\lab6）；该目录包含了测试工程的所有文件，其中lab6.dsw是工程文件，是工程的主文件。2）有向网的邻接阵实现（1）按照以上步骤完成新建工程（lab7）后，选择菜单“文件”-“新建”；（2）在打开的对话框中选中“文件”选项卡；（3）选择文件类型“C++SourceFile”；（4）在“文件名”处输入程序文件的名字graph；（5）按“确定”按钮，进入代码编写窗口。说明：完成以上步骤后，VC++6.0将在工程的文件目录下创建源代码文件（graph.cpp）。（6）输入以下参考程序代码段，仔细阅读程序注释，正确理解各函数的功能；#includestdio.h#includestring.h#defineMAXWEIGHT999//最大可能边权值(表示顶点间无边连接)#defineMAX_VERTEX_NUM20//图的最大可能顶点个数typedefcharVertexType[5];//顶点类型(定长字符串，最大长度4)typedefintArcType;//边(弧)数据类型//邻接阵类型typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点数组ArcTypearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,//顶点个数arcnum;//边条数}MGraph;//图类型//以下为邻接阵表示的图的基本操作函数//显示图的邻接矩阵voidDisplay(MGraphG){for(inti=0;iG.vexnum;i++){for(intj=0;jG.vexnum;j++)if(G.arcs[i][j]==MAXWEIGHT)printf(%5s,∞);//用∞表示无边连接elseprintf(%5d,G.arcs[i][j]);printf(\n);}}//判断两个顶点是否相同intequal(VertexTypev1,VertexTypev2){returnstrcmp(v1,v2)==0;}//查找顶点在顶点数组中的下标intlocate(MGraphG,VertexTypev){for(inti=0;iG.vexnum;i++)if(equal(G.vexs[i],v))returni;return-1;}//创建有向网（带权有向图）voidCreateGraph(MGraph*G){VertexTypev1,v2;ArcTypeweight;inti,j,k;printf(输入顶点数和边数：);scanf(%d%d,&G-vexnum,&G-arcnum);//创建顶点数组printf(逐行输入%d个顶点的名字：\n,G-vexnum);for(i=0;iG-vexnum;i++){scanf(%s,G-vexs[i]);}//初始化邻接阵for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++)G-arcs[i][j]=MAXWEIGHT;for(i=0;iG-vexnum;i++)G-arcs[i][i]=0;//不允许顶点有指向自身的循环边//接受邻接阵数据printf(逐行输入弧的起点、终点名字及边权值\n);for(k=0;kG-arcnum;k++){//输入顶点编号、边权值scanf(%s%s%d,v1,v2,&weight);//顶点对应数组元素下标i=locate(*G,v1);j=locate(*G,v2);G-arcs[i][j]=weight;}}（7）创建如下有向网的邻接阵存储结构，执行程序显示邻接阵，记录执行结果。21433）无向图的邻接阵实现修改上面创建邻接矩阵函数CreateGraph的代码，使之能够创建无向图。然后，创建如下无向图的邻接阵，执行程序显示邻接阵，记录执行结果。2、图的深度优先遍历（1）在上面的主函数(main)前输入以下代码，仔细阅读程序，正确理解各函数的功能；intvisited[MAX_VERTEX_NUM];//顶点访问标志数组//递归深度优先遍历voidDFS(MGraphG,inti){intn=G.vexnum;printf(%5s,G.vexs[i]);//访问顶点ivisited[i]=1;//设置顶点i的访问标志for(intj=0;jn;j++)//扫描第i行，寻找i的邻接顶点if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAXWEIGHT&&!visited[j])DFS(G,j);//递归访问i的邻接顶点j}15324//深度优先遍历主程序voidDFSTraverse(MGraphG){//对图g进行深度优先遍历intn=G.vexnum;for(inti=0;in;i++)visited[i]=0;//初始化顶点访问标志for(i=0;in;i++)if(visited[i]==0)DFS(G,i);}（3）修改主函数main代码，对上面图执行深度优先遍历并记录结果。（4）3、图的广度优先遍历编写代码实现基于邻接阵的广度优先遍历算法，并针对上面的图执行广度优先遍历并记录结果。提示：（1）可以采用类似深度优先遍历的算法框架，主函数BFSTraverse功能基本一样，子函数BFS利用队列实现；（2）队列的具体实现可参照实验4。代码：#includestdio.h#includestring.h#includemalloc.h//malloc()等#defineMAXWEIGHT999//最大可能边权值(表示顶点间无边连接)#defineMAX_VERTEX_NUM20//图的最大可能顶点个数typedefcharVertexType[5];//顶点类型(定长字符串，最大长度4)typedefintArcType;//边(弧)数据类型//邻接阵类型typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点数组ArcTypearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,//顶点个数arcnum;//边条数}MGraph;//图类型//队列元素的数据类型//循环队列类型typedefstructQNode{int*elem;//队列元素存储数组intfront;//头指针，若队列不空，则指向队列头元素intrear;//尾指针，若队列不空，则指向队列尾元素的下一个位置intqueuesize;}SqQueue;//初始化循环队列voidInitQueue(SqQueue*q){q-elem=(int*)malloc((MAX_VERTEX_NUM+1)*sizeof(int));//初始化队头、队尾q-front=0;q-rear=0;q-queuesize=MAX_VERTEX_NUM;}//队列空判定(若队空返回1，否则返回0)intQueueEmpty(SqQueueq){//以下是你的代码if(q.rear==q.front)return1;return0;//以上是你的代码}//入队intEnQueue(SqQueue*q,inte){if(((q-rear+1)%q-queuesize)==q-front)return0;//队满则返回0q-elem[q-rear]=e;//队尾处放入新元素q-rear=(q-rear+1)%q-queuesize;//循环递增队尾return1;}//出队intDeQueue(SqQueue*q,int*e){if(q-front==q-rear)return0;//队空则返回0(表示出错)*e=q-elem[q-front];//取队头元素q-front=(q-front+1)%q-queuesize;//循环递增队头return1;}//销毁队列voidDestoryQueue(SqQueue*q){free(q-elem);q-elem=NULL;q-front=0;q-rear=0;q-queuesize=0;}//以下为邻接阵表示的图的基本操作函数//显示图的邻接矩阵voidDisplay(MGraphG){for(inti=0;iG.vexnum;i++){for(intj=0;jG.vexnum;j++)if(G.arcs[i][j]==MAXWEIGHT)printf(%5s,∞);//用∞表示无边连接elseprintf(%5d,G.arcs[i][j]);printf(\n);}}//判断两个顶点是否相同intequal(VertexTypev1,VertexTypev2){returnstrcmp(v1,v2)==0;}//查找顶点在顶点数组中的下标intlocate(MGraphG,VertexTypev){for(inti=0;iG.vexnum;i++)if(equal(G.vexs[i],v))returni;return-1;}//创建有向网（带权有向图）/*voidCreateGraph(MGraph*G){VertexTypev1,v2;ArcTypeweight;inti,j,k;printf(输入顶点数和边数：);scanf(%d%d,&G-vexnum,&G-arcnum);//创建顶点数组printf(逐行输入%d个顶点的名字：\n,G-vexnum);for(i=0;iG-vexnum;i++){scanf(%s,G-vexs[i]);}//初始化邻接阵for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++)G-arcs[i][j]=MAXWEIGHT;for(i=0;iG-vexnum;i++)G-arcs[i][i]=0;//不允许顶点有指向自身的循环边//接受邻接阵数据printf(逐行输入弧的起点、终点名字及边权值\n);for(k=0;kG-arcnum;k++){//输入顶点编号、边权值scanf(%s%s%d,v1,v2,&weight);//顶点对应数组元素下标i=locate(*G,v1);j=locate(*G,v2);G-arcs[i][j]=weight;}}*/voidCreateGraph(MGraph*G){VertexTypev1,v2;inti,j,k;printf(输入顶点数和边数：);scanf(%d%d,&G-vexnum,&G-arcnum);//创建顶点数组printf(逐行输入%d个顶点的名字：\n,G-vexnum);for(i=0;iG-vexnum;i++){scanf(%s,G-vexs[i]);}//初始化邻接阵for(i=0;iG-vexnum;i++)for(j=0;jG-vexnum;j++)G-arcs[i][j]=MAXWEIGHT;for(i=0;iG-vexnum;i++)G-arcs[i][i]=0;//不允许顶点有指向自身的循环边//接受邻接阵数据