搜索
《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院1常熟理工学院《数据结构与算法》实验指导与报告书_2017-2018_____学年第__1__学期专业：物联网工程实验名称：实验七图实验地点：N6-210指导教师：聂盼红计算机科学与工程学院2017《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院2实验七图【实验目的】1、掌握图的邻接矩阵和邻接表表示。2、掌握图的深度优先和广度优先搜索方法。3、掌握图的最小生成树Prim算法。4、掌握图的拓扑排序算法。5、掌握图的单源最短路径dijkstra算法。【实验学时】4-6学时【实验预习】回答以下问题：1、写出图7-1无向图的邻接矩阵表示。2、写出图7-2有向图的邻接表表示。3、写出图7-1的深度优先搜索序列和广度优先搜索序列。深度优先搜索序列：A,C,B,D,E,F,G,H广度优先搜索序列：A,B,C,D,E,F,G,H,EFBACDABCGFDEH《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院34、写出图7-2的拓扑序列，说明该有向图是否有环？拓扑序列:EABCD该有向图没有环5、根据图7-3，写出其最小生成树。图7-3无向带权图G36、根据图7-4，求从顶点A到其他顶点的单源最短路径。ABCDEF1006020301050105X`图7-4有向带权图G4单源最短路径：A,C=10:ACA,D=50:AEDA,E=30:AEA,F=60:AEDF【实验内容和要求】1、编写程序exp7_1.c，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索。以图7-1的无向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）CFDBAE6215566345《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院4exp7_1.c参考程序如下：#includestdio.h#defineN20#defineTRUE1#defineFALSE0#defineMAX100intvisited[N];/*访问标志数组*/typedefstruct{/*辅助队列的定义*/intdata[N];intfront,rear;}queue;typedefstruct{/*图的邻接矩阵表示*/intvexnum,arcnum;charvexs[N];intarcs[N][N];}MGraph;voidcreateGraph(MGraph*g);/*建立一个无向图的邻接矩阵*/《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院5voiddfs(inti,MGraph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(MGraph*g);/*深度优先搜索整个图*/voidbfs(intk,MGraph*g);/*从第k个顶点广度优先搜索*/voidtbfs(MGraph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识数组*/voidcreateGraph(MGraph*g){/*建立一个无向图的邻接矩阵*/inti=0,j,e=0;charv;g-vexnum=0;g-arcnum=0;printf(\n输入顶点序列(以#结束)：\n);while((v=getchar())!='#'){g-vexs[i]=v;/*读入顶点信息*/i++;}g-vexnum=i;/*顶点数目*/for(i=0;ig-vexnum;i++)/*邻接矩阵初始化*/for(j=0;jg-vexnum;j++)g-arcs[i][j]=0;/*（1）-邻接矩阵元素初始化为0*/printf(\n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：\n);scanf(%d,%d,&i,&j);/*读入边(i,j)*/while(i!=-1){/*读入i为－1时结束*/g-arcs[i][j]=1;/*（2）-i,j对应边等于1*/e++;scanf(%d,%d,&i,&j);}g-arcnum=e;/*边数目*/}/*createGraph*//*（3）---从第i个顶点出发深度优先搜索，补充完整算法*/voiddfs(inti,MGraph*g){intj;printf(%c,g-vexs[i]);visited[i]=1;for(j=0;jg-vexnum;j++)if((g-arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}/*dfs*/《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院6voidtdfs(MGraph*g){/*深度优先搜索整个图*/inti;printf(\n从顶点%C开始深度优先搜索序列：,g-vexs[0]);for(i=0;ig-vexnum;i++)if(visited[i]!=1)/*（4）---对尚未访问过的顶点进行深度优先搜索*/dfs(i,g);printf(\n);}/*tdfs*/voidbfs(intk,MGraph*g){/*从第k个顶点广度优先搜索*/inti,j;queueqlist,*q;q=&qlist;q-rear=0;q-front=0;printf(%c,g-vexs[k]);visited[k]=TRUE;q-data[q-rear]=k;q-rear=(q-rear+1)%N;while(q-rear!=q-front){/*当队列不为空，进行搜索*/i=q-data[q-front];q-front=(q-front+1)%N;for(j=0;jg-vexnum;j++)if((g-arcs[i][j]==1)&&(!visited[j])){printf(%c,g-vexs[j]);visited[j]=TRUE;q-data[q-rear]=j;/*（5）---刚访问过的结点入队*/q-rear=(q-rear+1)%MAX;/*（6）---修改队尾指针*/}}}/*bfs*/voidtbfs(MGraph*g){/*广度优先搜索整个图*/inti;printf(\n从顶点%C开始广度优先搜索序列：,g-vexs[0]);for(i=0;ig-vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);/*从顶点i开始广度优先搜索*/printf(\n);}/*tbfs*/voidinit_visit(){/*初始化访问标识数组*/inti;《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院7for(i=0;iN;i++)visited[i]=FALSE;}intmain(){MGraphga;inti,j;printf(***********图邻接矩阵存储和图的遍历***********\n);printf(\n1-输入图的基本信息：\n);createGraph(&ga);printf(\n2-无向图的邻接矩阵：\n);for(i=0;iga.vexnum;i++){for(j=0;jga.vexnum;j++)printf(%3d,ga.arcs[i][j]);printf(\n);}printf(\n3-图的遍历：\n);init_visit();/*初始化访问数组*/tdfs(&ga);/*深度优先搜索图*/init_visit();tbfs(&ga);/*广度优先搜索图*/return0;}2、编写程序exp7_2.c，实现图的邻接表存储和拓扑排序算法。以图7-2的有向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院8exp7_2.c程序代码参考如下：#includestdio.h#includemalloc.h#defineN20/*图的邻接表：邻接链表结点*/typedefstructEdgeNode{intadjvex;/*顶点序号*/structEdgeNode*next;/*下一个结点的指针*/}EdgeNode;/*图的邻接表：邻接表*/typedefstructVNode{chardata;/*顶点信息*/intind;/*顶点入度*/structEdgeNode*link;/*指向邻接链表指针*/}VNode;typedefstructALgraph{/*图的邻接表*/intvexnum,arcnum;/*顶点数、弧数*/VNodeadjlist[N];}ALGraph;voidcreateGraph_list(ALGraph*g);/*建立有向图的邻接表*/voidtopSort(ALGraph*g);/*拓扑排序*//*建立有向图的邻接表*/voidcreateGraph_list(ALGraph*g){inti,j,e;charv;EdgeNode*s;i=0;e=0;printf(\n输入顶点序列(以#结束)：\n);while((v=getchar())!='#'){g-adjlist[i].data=v;/*读入顶点信息*/g-adjlist[i].link=NULL;g-adjlist[i].ind=0;i++;}g-vexnum=i;/*建立邻接链表*/printf(\n请输入弧的信息(顶点序号,顶点序号)，以(-1,-1)结束:\n);scanf(%d,%d,&i,&j);while(i!=-1){s=(structEdgeNode*)malloc(sizeof(EdgeNode));s-adjvex=j;《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院9s-next=g-adjlist[i].link;;/*（1）s插入链表*/g-adjlist[i].link=s;g-adjlist[j].ind++;/*（2）顶点j的入度加1*/e++;scanf(%d,%d,&i,&j);}g-arcnum=e;}/*createGraph_list*/voidtopSort(ALGraph*g){/*拓扑排序*/inti,j,k,top=0,m=0,s[N];/*m为拓扑排序输出的结点数*/EdgeNode*p;for(i=0;ig-vexnum;i++)if(!g-adjlist[i].ind){/*（3）入度为0的顶点入栈*/s[top++]=i;}printf(\n输出拓扑序列：);while(top0){j=s[--top];printf(%c,g-adjlist[j].data);m++;p=g-adjlist[j].link;while(p!=NULL){k=p-adjvex;g-adjlist[k].ind--;/*顶点k入度减1*/if(g-adjlist[k].ind==0)/*顶点k入度为0，进栈*/s[top++]=k;p=p-next;}}printf(\n共输出%d个顶点\n,m);if(mg-vexnum)/*（4）当输出顶点数小于图的顶点数，表示有环*/printf(图中有环！);elseprintf(图中无环！);}/*topSort*/intmain(){ALGraphg;inti;EdgeNode*s;《数据结构与算法》实验指导V2017常熟理工学院计算机科学与工程学院10printf(***********图的邻接表存储结构和拓扑排序***********\n);printf(\n1-输入图的基本信息：\n);createGraph_list(&g);/*创建图的邻接表存储结构*/printf(\n2-图的邻接表:);for(i=0;ig.vexnum;i++){/*输出图的邻接表存储结构*/printf(\n%c,%d:,g.adjlist[i].data,