《数据结构图.pdf》由会员分享，可在线阅读，更多相关《数据结构图.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、WORD 格式专业资料整理数据结构与算法实验指导V2017 常熟理工学院数据结构与算法实验指导与报告书_2017-2018_ 学年第 _1_学期专业：物联网工程实验名称：实验七图实验地点：N6-210 指导教师：聂盼红计算机科学与工程学院2017 常熟理工学院计算机科学与工程学院1WORD 格式专业资料整理数据结构与算法实验指导V2017 实验七图【实验目的】1、掌握图的邻接矩阵和邻接表表示。2、掌握图的深度优先和广度优先搜索方法。3、掌握图的最小生成树Prim 算法。4、掌握图的拓扑排序算法。5、掌握图的单源最短路径dijkstra算法。【实验学时】4-6 学时【实验预习】回答以下问题：1、
2、写出图 7-1 无向图的邻接矩阵表示。G A F C B E D H 2、写出图 7-2 有向图的邻接表表示。F E C B D A WORD 格式专业资料整理3、写出图 7-1 的深度优先搜索序列和广度优先搜索序列。深度优先搜索序列：A,C,B,D,E,F,G,H 广度优先搜索序列：A,B,C,D,E,F,G,H,常熟理工学院计算机科学与工程学院2WORD 格式专业资料整理数据结构与算法实验指导V2017 4、写出图 7-2 的拓扑序列，说明该有向图是否有环？拓扑序列:EABCD 该有向图没有环5、根据图 7-3，写出其最小生成树。A 65 1 BD 5 5 C 3 6 2 4 6 EF 图
3、 7-3 无向带权图G3 6、根据图 7-4，求从顶点A到其他顶点的单源最短路径。F 60 100 30 AE 1020 10 D B 50 5 C X图 7-4 有向带权图G4 单源最短路径：=10:AC=50:AED=30:AE=60:AEDF WORD 格式专业资料整理【实验内容和要求】1、编写程序exp7_1.c，实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索。以图 7-1 的无向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）常熟理工学院计算机科学与工程学院3WORD 格式专业资料整理数据结构与算法实验指导V2017 exp7_1.c 参考程序如下：#i
4、nclude#defineN20#defineTRUE1#defineFALSE0#defineMAX100 intvisitedN;/*访问标志数组*/typedefstruct/*辅助队列的定义*/intdataN;intfront,rear;queue;typedefstruct/*图的邻接矩阵表示*/intvexnum,arcnum;charvexsN;intarcsNN;MGraph;voidcreateGraph(MGraph*g);/*建立一个无向图的邻接矩阵*/常熟理工学院计算机科学与工程学院4WORD 格式专业资料整理数据结构与算法实验指导V2017 voiddfs(inti
5、,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-vexsi
6、=v;/*读入顶点信息*/i+;g-vexnum=i;/*顶点数目*/for(i=0;ivexnum;i+)/*邻接矩阵初始化*/for(j=0;jvexnum;j+)g-arcsij=0;/*（1）-邻接矩阵元素初始化为0*/printf(n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：n);scanf(%d,%d,&i,&j);/*读入边(i,j)*/while(i!=-1)/*读入 i 为 1 时结束*/g-arcsij=1;/*（2）-i,j对应边等于1*/e+;scanf(%d,%d,&i,&j);g-arcnum=e;/*边数目*/*createGraph*/*（3）-
7、从第 i 个顶点出发深度优先搜索，补充完整算法*/voiddfs(inti,MGraph*g)intj;printf(%c,g-vexsi);visitedi=1;for(j=0;jvexnum;j+)if(g-arcsij=1)&(!visitedj)dfs(j,g);/*dfs*/常熟理工学院计算机科学与工程学院5WORD 格式专业资料整理数据结构与算法实验指导V2017 voidtdfs(MGraph*g)/*深度优先搜索整个图*/inti;printf(n从顶点%C 开始深度优先搜索序列：,g-vexs0);for(i=0;ivexnum;i+)if(visitedi!=1)/*（4）
8、-对尚未访问过的顶点进行深度优先搜索*/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-vexsk);visitedk=TRUE;q-dataq-rear=k;q-rear=(q-rear+1)%N;while(q-rear!=q-front)/*当队列不为空，进行搜索*/i=q-dataq-front;q-front=(q-front+1)%N;for(j=0;jvexnum;j+)if
9、(g-arcsij=1)&(!visitedj)printf(%c,g-vexsj);visitedj=TRUE;q-dataq-rear=j;/*（5）-刚访问过的结点入队*/q-rear=(q-rear+1)%MAX;/*（6）-修改队尾指针*/*bfs*/voidtbfs(MGraph*g)/*广度优先搜索整个图*/inti;printf(n从顶点%C 开始广度优先搜索序列：,g-vexs0);for(i=0;ivexnum;i+)if(visitedi!=TRUE)bfs(i,g);/*从顶点 i 开始广度优先搜索*/printf(n);/*tbfs*/voidinit_visit()
10、/*初始化访问标识数组*/inti;常熟理工学院计算机科学与工程学院6WORD 格式专业资料整理数据结构与算法实验指导V2017 for(i=0;iN;i+)visitedi=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.arcsij);printf(n);printf(n3-图的遍历：n);in
11、it_visit();/*初始化访问数组*/tdfs(&ga);/*深度优先搜索图*/init_visit();tbfs(&ga);/*广度优先搜索图*/return0;2、编写程序exp7_2.c，实现图的邻接表存储和拓扑排序算法。以图 7-2 的有向图为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）常熟理工学院计算机科学与工程学院7WORD 格式专业资料整理数据结构与算法实验指导V2017 exp7_2.c 程序代码参考如下：#include#include#defineN20/*图的邻接表：邻接链表结点*/typedefstructEdgeNode intadjve
12、x;/*顶点序号*/structEdgeNode*next;/*下一个结点的指针*/EdgeNode;/*图的邻接表：邻接表*/typedefstructVNode chardata;/*顶点信息*/intind;/*顶点入度*/structEdgeNode*link;/*指向邻接链表指针*/VNode;typedefstructALgraph/*图的邻接表*/intvexnum,arcnum;/*顶点数、弧数*/VNodeadjlistN;ALGraph;voidcreateGraph_list(ALGraph*g);/*建立有向图的邻接表*/voidtopSort(ALGraph*g);/
13、*拓扑排序*/*建立有向图的邻接表*/voidcreateGraph_list(ALGraph*g)inti,j,e;charv;EdgeNode*s;i=0;e=0;printf(n输入顶点序列(以#结束)：n);while(v=getchar()!=#)g-adjlisti.data=v;/*读入顶点信息*/g-adjlisti.link=NULL;g-adjlisti.ind=0;i+;g-vexnum=i;/*建立邻接链表*/printf(n请输入弧的信息(顶点序号,顶点序号)，以(-1,-1)结束:n);scanf(%d,%d,&i,&j);while(i!=-1)s=(struct
14、EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=j;常熟理工学院计算机科学与工程学院8WORD 格式专业资料整理数据结构与算法实验指导V2017 s-next=g-adjlisti.link;/*（1）s 插入链表*/g-adjlisti.link=s;g-adjlistj.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,sN;/*m为拓扑排序输出的结点数*
15、/EdgeNode*p;for(i=0;ivexnum;i+)if(!g-adjlisti.ind)/*（3）入度为 0 的顶点入栈*/stop+=i;printf(n输出拓扑序列：);while(top0)j=s-top;printf(%c,g-adjlistj.data);m+;p=g-adjlistj.link;while(p!=NULL)k=p-adjvex;g-adjlistk.ind-;/*顶点 k 入度减 1*/if(g-adjlistk.ind=0)/*顶点 k 入度为 0，进栈*/stop+=k;p=p-next;printf(n共输出%d个顶点 n,m);if(mvexnu
16、m)/*（4）当输出顶点数小于图的顶点数，表示有环*/printf(图中有环！);else printf(图中无环！);/*topSort*/intmain()ALGraphg;inti;EdgeNode*s;常熟理工学院计算机科学与工程学院9WORD 格式专业资料整理数据结构与算法实验指导V2017 printf(*图的邻接表存储结构和拓扑排序*n);printf(n1-输入图的基本信息：n);createGraph_list(&g);/*创建图的邻接表存储结构*/printf(n2-图的邻接表:);for(i=0;i%d,s-adjvex);s=s-next;printf(n);print
17、f(n3-根据图的邻接表实现拓扑排序：n);topSort(&g);/*进行拓扑排序*/return0;（3）调试下面给出的图的信息，写出运行结果，画出该有向图。ABCDEF#1,0 1,3 2,1 2,5 3,2 3,4 3,5 4,0 5,0 5,1 5,4-1,-1 常熟理工学院计算机科学与工程学院10WORD 格式专业资料整理数据结构与算法实验指导V2017 3、编写程序exp7_3.c，实现带权图的存储、图的最小生成树及单源最短路径算法。以图 7-3（求该图最小生成树）和图7-4（求该图的单源最短路径）为例，补充完整程序，调试运行并写出运行结果。运行结果：（包括输入数据）exp7_3
18、.c 程序代码参考如下：常熟理工学院计算机科学与工程学院11WORD 格式专业资料整理数据结构与算法实验指导V2017#include#defineN20#defineTRUE1#defineINF10002766/*邻接矩阵中的无穷大元素*/#defineINFIN10002767/*比无穷大元素大的数*/typedefstruct/*图的邻接矩阵表示*/intvexnum,arcnum;charvexsN;intarcsNN;MGraph;voidprintPath(MGraphg,intstartVex,intEndVex,intpathN);/*打印最短路径*/voidcreateMG
19、raph_w(MGraph*g,intflag);/*建带权图的邻接矩阵*/voidprim(MGraph*g,intu);/*求最小生成树Prim 算法，u 为出发顶点*/voiddijkstra(MGraphg,intv);/*dijkstra算法求单源最短路径*/voidcreateMGraph_w(MGraph*g,intflag)/*建带权图的邻接矩阵,若 flag为 1 则为无向图，flag为 0 为有向图*/inti,j,w;charv;g-vexnum=0;g-arcnum=0;i=0;printf(n输入顶点序列(以#结束)：n);while(v=getchar()!=#)g
20、-vexsi=v;/*读入顶点信息*/i+;g-vexnum=i;for(i=0;i6;i+)/*邻接矩阵初始化*/for(j=0;jarcsij=INF;printf(n输入边的信息：(顶点，顶点，权值)，以(-1,-1,-1)结束 n);scanf(%d,%d,%d,&i,&j,&w);/*读入边(i,j,w)*/while(i!=-1)/*读入 i 为 1 时结束*/g-arcsij=w;if(flag=1)g-arcsji=w;scanf(%d,%d,%d,&i,&j,&w);/*createMGraph_w*/voidprim(MGraph*g,intu)/*求最小生成树Prim 算
21、法，u 为出发顶点*/常熟理工学院计算机科学与工程学院12WORD 格式专业资料整理数据结构与算法实验指导V2017 intlowcostN,closestN,i,j,k,min;for(i=0;ivexnum;i+)/*求其他顶点到出发顶点u 的权*/lowcosti=g-arcsuj;/*（1）-顶点 i 到 u 的代价最小的边权值*/closesti=u;lowcostu=0;printf(n最小生成树：n);for(i=1;ivexnum;i+)/*循环求最小生成树中的各条边*/min=INFIN;for(j=0;jvexnum;j+)/*选择得到一条代价最小的边*/if(lowcos
22、tj!=0&lowcostjvexsclosestk,g-vexsk,lowcostk);/*输出该边*/lowcostk=0;/*顶点 k 纳入最小生成树*/for(j=0;jvexnum;j+)/*求其他顶点到顶点k 的权*/if(g-arcskj!=0&g-arcskjarcskj;/*（3）-其他顶点到k 的代价最小的边权值*/closestj=k;/*prim*/voidprintPath(MGraphg,intstartVex,intEndVex,intpathN)intstackN,top=0;/堆栈inti,k,j;intflagN;/输出路径顶点标志k=EndVex;for(
23、i=0;i0)/找 j 到 k 的路径for(i=0;i%c(%d),g.vexsi,g.arcsji);/输出 j 到 k 路径顶点 i flagi=1;j=i;k=stack-top;break;常熟理工学院计算机科学与工程学院13WORD 格式专业资料整理数据结构与算法实验指导V2017 else if(i!=k)stacktop+=i;if(flagk=0)printf(-%c(%d),g.vexsk,g.arcsjk);voiddijkstra(MGraphg,intv)/*dijkstra算法求单源最短路径*/intsN,pathNN,distN;intmindis,i,j,u,k
24、;for(i=0;ig.vexnum;i+)disti=g.arcsvi;si=0;for(j=0;jg.vexnum;j+)pathij=0;if(distiINF)pathiv=1;pathii=1;distv=0;sv=1;for(i=0,u=1;ig.vexnum;i+)mindis=INFIN;for(j=0;jg.vexnum;j+)if(sj=0)if(distjmindis)u=j;mindis=distj;su=1;for(j=0;jg.vexnum;j+)if(sj=0)&distu+g.arcsujdistj)distj=distu+g.arcsuj;for(k=0;k到
25、各顶点的最短路径n,g.vexsv);for(i=0;i顶点%c：,g.vexsv,g.vexsi);常熟理工学院计算机科学与工程学院14WORD 格式专业资料整理数据结构与算法实验指导V2017 if(disti=INF|disti=0)printf(无路径);else printf(%d,disti);printf(经过顶点：);printPath(g,v,i,path);/输出 v 到 i 的路径 /*dijkstra*/intmain()intselect;MGraphga;do printf(n*MENU*n);printf(1.图的最小生成树-Prim 算法 n);printf(2
26、.图的单源最短路径-dijstra算法 n);printf(0.EXIT);printf(n*MENU*n);printf(ninputchoice:);scanf(%d,&select);getchar();switch(select)case1:printf(n1-图的最小生成树-Prim 算法n);printf(n输入带权图的基本信息：n);createMGraph_w(&ga,1);prim(&ga,0);break;case2:printf(n2-图的单源最短路径-dijstra算法 n);printf(n输入带权图的基本信息：n);createMGraph_w(&ga,0);dij
27、kstra(ga,0);break;default:break;while(select);return0;【拓展实验】4、编写算法，实现最小生成树的Kruskal算法。提示：常熟理工学院计算机科学与工程学院15WORD 格式专业资料整理数据结构与算法实验指导V2017 Kruskal算法实现的基本步骤：（1）需要对图中所有的边进行排序，因此需要借助一个辅助数组edge 来存储按权值由小到大排序的边。包括边的权值、边的起点和终点。（2）每加入一条边，需要判断该边的两个顶点是否处在同一连通分量上，可以利用数组 parents来表示各顶点的状况，parentsi=i；初始值设置为各自的顶点值，表示
28、各顶点自成一连通分量。当加入该边，需要对该边的边头顶点和边尾顶点的parents值相等。5、编写算法，实现图的最短路径Floyd 算法。提示：弗洛伊德算法的基本步骤：对有向图采用带权邻接矩阵存储，同时定义一个二维数组ANN 存放顶点 i 到 j 的最短路径。（1）初始化 Aij=arcsij;（2）考虑 vi 和 vj 之间的路径，是否存在途经vk 的路径（vi,vk,vj),若存在，比较Aik+AKj和 Aij的距离，较小送Aij；重复上步，取vk 为图中所有顶点，直到比较完毕。同时还必须定义一个矩阵记录最短路径经过的顶点。voidFloyd()Inti,j,k;for(k=1;k=n;k+
29、)for(i=1;i=n;i+)for(j=1;jDi,k+Dk,j)Di,j=Di,k+Dk,j;6、编写算法，实现图的关键路径算法。提示：基于邻接矩阵的关键路径的求解步骤：(1)对 AOE网进行拓扑排序，同时按拓扑序列的次序求出各顶点事件的最早发生时间ve，若网中存在回路，则算法终止，否则执行步骤(2)；(2)按拓扑序列的逆序求出各顶点事件的最迟发生时间vl；(3)根据各顶点事件的ve 和 vl 值，求出各顶点活动ai 的最早发生时间e(i)和最迟发生时间 l(i)。若 e(i)l(i)，则 ai 为关键活动。【实验小结】通过实验七图，我学会了的邻接矩阵和邻接表表示,学会了图的深度优先和广度优先搜索方法以及图的最小生成树Prim 算法、图的拓扑排序算法。常熟理工学院计算机科学与工程学院16