图的基本操作与应用

浙江大学城市学院实验报告课程名称数据结构实验项目名称实验六图的基本操作与应用实验成绩指导老师（签名）日期一.实验目的和要求1、掌握图的存储结构：邻接矩阵、邻接表。2、掌握图的深度优先与广度优先两个搜素算法。3、学会对图的存储结构进行基本操作。4、加强综合程序的分析、设计能力。二.实验内容1、现有14个人（分别用字母A、B、...N表示），他们相互之间的朋友关系如图所示（有线相连表示是朋友关系），请分别用邻接矩阵与邻接表表示该关系图，并完成以下功能。①以邻接矩阵表示，在此结构上完成：创建此图；输出此图的邻接矩阵；输出从A出发的深度优先搜索序列；输出从A出发的广度优先搜索序列；输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=‘A’、p2=‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。）②以邻接表表示，在此结构上完成：创建此图；输出此图的邻接表；输出从A出发的深度优先搜索序列；输出从A出发的广度优先搜索序列；输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径；（如输入p1=‘A’、p2=‘N’，则A与N不是直接朋友关系，但可以（不唯一）通过A-B-F-K-N方式联系到N。）③建立头文件AdjMatrix.h和AdjLink.h，分别包含邻接矩阵结构和邻接表结构的操作实现函数，建立主程序文件test6.cpp，在主函数中通过调用来实现上述功能。④自行增加合适的功能，可作为额外的实验成绩进行加分（例如考虑添加或删除一对朋友关系；找出朋友最多的那个人；上面找到A到N的联系路径，若要求找到一条最短的路线怎么找等等）。2、以小组为单位认真填写实验报告，实验报告必须包括各类数据类型的结构定义说明，各类数据的组织方式，系统的功能结构，各个操作的定义以及实现方法，运行结果与分析，难点如何解决，存在问题以及可改进之处等。同时，在实验报告中需写明小组每位同学的分工，得分（小组总分不超过12分）等。实验报告文件取名为report6.doc。每组还必须制作一个答辩PPT以备答辩。3、由组长上传实验报告文件report6.doc、源程序文件test6.cpp及AdjMatrix.h和AdjLink.h到BB平台上。功能模块图：主菜单创建此图输出此图的邻接表或邻接矩阵查找朋友最多的人判断两人是否为朋友输出从A出发的广度优先搜索序列输出从A出发的深度优先搜索序列邻接表邻接矩阵函数调用结构图：左侧为邻接矩阵的相关函数，右侧为邻接表的相关函数结构体定义typedefstructMGraph{statusvexs[MAXMAX];intarcs[MAXMAX][MAXMAX];intvernum,arcnum;}MGraph;//邻接矩阵//邻接表typedefstructArcNode{intadjvex;//下标structArcNode*nextarc;}ArcNode;typedefstructVNode{statusdata;ArcNode*firstarc;mainInitMGraphShowMGraphmenuInitALGraphFindALGraphDFSTraverseMGraphShowALGraphBFSTraverseMGraphDFSTraverseALGraphFindMGraphJudgeALGraphJudgeMGraphBFSTraverseALGraph}VNode,AdjList[MAXMAX];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//队列typedefstruct{int*data;intrear;intfront;}sqQueue;实现思路深度优先搜索序列利用一个数组来记录顶点是否被访问，对未访问的邻接顶点进行递归，直至所有顶点均被访问。广度优先搜索序列利用一个数组来记录顶点是否被访问，未被访问的顶点及其邻接点进队列，并且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至所有顶点均被访问，访问完后出队列至队空。运行结果与分析输入数字，进行对应的操作输入1创建此图，输入1或2建立邻接矩阵或邻接表可改进之处可以增加查找两人的最短路径；可以增加对错误信息的处理；源代码test6.cpp#includestdio.h#includestdlib.h#includestring.h#includetime.h#includewindows.h#defineOK1#defineFALSE0#defineTRUE1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineMAXMAX100intMAX=14;typedefstruct{charname;}status;typedefstructMGraph{statusvexs[MAXMAX];intarcs[MAXMAX][MAXMAX];intvernum,arcnum;}MGraph;//邻接矩阵//邻接表typedefstructArcNode{intadjvex;//下标structArcNode*nextarc;}ArcNode;typedefstructVNode{statusdata;ArcNode*firstarc;}VNode,AdjList[MAXMAX];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//队列typedefstruct{int*data;intrear;intfront;}sqQueue;intvisit[MAXMAX];//访问标志数组intv;#includeQueue.h#includeAdjMatrix.h#includeAdjLink.hvoidmenu(){printf(1.创建此图\n);printf(2.输出此图的邻接表或邻接矩阵\n);printf(3.输出从A出发的深度优先搜索序列\n);printf(4.输出从A出发的广度优先搜索序列\n);printf(5.输入两个人p1、p2，判断此两人是否为朋友关系，若不是，给出一种从p1能找到p2的路径\n);printf(6.查找朋友最多的那个人\n);printf(0.退出\n);printf(输入您想进行的操作\n);}intmain(){MGraphM;ALGraphA;intn,a;menu();while(1){scanf(%d,&n);getchar();if(n==1){system(CLS);MAX=14;printf(输入1建立邻接矩阵；输入2建立邻接表\n);scanf(%d,&a);getchar();if(a==1){InitMGraph(M);}if(a==2){InitALGraph(A);}printf(输入9返回，输入0退出\n);}if(n==2){system(CLS);if(a==1){ShowMGraph(M);}if(a==2){ShowALGraph(A);}printf(输入9返回，输入0退出\n);}if(n==3){system(CLS);if(a==1){v=0;DFSTraverseMGraph(M,v);}if(a==2){v=0;DFSTraverseALGraph(A,v);}printf(输入9返回，输入0退出\n);}if(n==4){system(CLS);if(a==1){BFSTraverseMGraph(M,v);}if(a==2){BFSTraverseALGraph(A,v);}printf(输入9返回，输入0退出\n);}if(n==5){system(CLS);if(a==1){JudgeMGraph(M,v);}if(a==2){JudgeALGraph(A,v);}printf(输入9返回，输入0退出\n);}if(n==6){system(CLS);if(a==1){FindMGraph(M);}if(a==2){FindALGraph(A);}printf(输入9返回，输入0退出\n);}if(n==9){system(CLS);menu();}if(n==0){break;}}}Queue.hintInitQueue(sqQueue&L)//创建队列{L.data=(int*)malloc(MAXMAX*sizeof(int));L.rear=0;L.front=0;}intEnQueue(sqQueue&L,intv)//进队列{L.data[L.rear]=v;L.rear=(L.rear+1)%MAXMAX;}intDeQueue(sqQueue&L,int&u)//出队列{u=L.data[L.front];L.front=(L.front+1)%MAXMAX;}intQueueEmpty(sqQueue&L){if(L.front==L.rear){return1;}return0;}AdjMatrix.hintInitMGraph(MGraph&M)//创建此图{inti,j;M.vexs[0].name='A';M.vexs[1].name='B';M.vexs[2].name='C';M.vexs[3].name='D';M.vexs[4].name='E';M.vexs[5].name='F';M.vexs[6].name='G';M.vexs[7].name='H';M.vexs[8].name='I';M.vexs[9].name='J';M.vexs[10].name='K';M.vexs[11].name='L';M.vexs[12].name='M';M.vexs[13].name='N';for(i=0;iMAX;i++){for(j=0;jMAX;j++){M.arcs[i][j]=0;//将邻接矩阵清空}}M.arcs[0][1]=1;M.arcs[0][2]=1;M.arcs[1][0]=1;M.arcs[1][5]=1;M.arcs[2][0]=1;M.arcs[2][7]=1;M.arcs[3][4]=1;M.arcs[3][5]=1;M.arcs[4][3]=1;M.arcs[4][8]=1;M.arcs[4][7]=1;M.arcs[5][1]=1;M.arcs[5][6]=1;M.arcs[5][10]=1;M.arcs[5][9]=1;M.arcs[5][3]=1;M.arcs[6][5]=1;M.arcs[7][2]=1;M.arcs[7][4]=1;M.arcs[7][11]=1;M.arcs[7][12]=1;M.arcs[8][4]=1;M.arcs[8][9]=1;M.arcs[8][12]=1;M.arcs[9][5]=1;M.arcs[9][10]=1;M.arcs[9][8]=1;M.arcs[10][5]=1;M.arcs[10][13]=1;M.arcs[10][9]=1;M.arcs[11][7]=1;M.arcs[12][8]=1;M.arcs[12][13]=1;M.arcs[12][7]=1;M.arcs[13][10]=1;M.arcs[13][12]=1;M.arcnum=18;M.vernum=14;}intShowMGraph(MGraph&M)//输出此图的邻接矩阵{inti,j;for(i=0;iMAX;i++){for(j=0;jMAX;j++){printf(%d,M.arcs[i][j]);}printf(\n);}}intDFSMGraph(MGraph&M,intv)//深度优先{inti;visit[v]=TRUE;printf(姓名:%c\n,M.vexs[v].name);for(i=0;i