数据结构习题解析与实训 第七章.doc

第7章 图图是另一种重要的非线性结构,它比树的结构更复杂,更灵活。习题中涉及到图的两种常用的存储结构即图的邻接矩阵和邻接链表。这些习题的目的主要让读者掌握图的深度遍历和广度遍历的算法,同时加深对图的几个应用问题的算法的理解。7.1习题解析【习题1】连通图上实现广度优先遍历题目要求:在以邻接链表为存储结构的无向图上,实现无向图的广度优先遍历算法。【习题1】和【习题2】是在连通图上实现图的广度优先遍历算法和深度优先遍历算法。这两个算法同样适用于对非连通图的遍历,稍加分析和设计,就可计算出非连通图上有几个连通分量并给出对每个连通分量的遍历结果。程序的实现留给读者自己完成。结构说明:#defineVEXTYPEint#defineMAXLEN40typedefstructnode3/表结点结构/intadjvex;/存放与表头结点相邻接的顶点在数组中的序号/structnode3next;/指向与表头结点相邻接的下一个顶点的表结点/EDGENODE;typrdefstructEXTYPEvertex;/存放图中顶点的信息/EDGENODElink;/指针指向对应的单链表中的表结点/VEXNODE;typedefstruct 第7章图l77EXNODEadjlistMAXLEN;/邻接链表表头向量/intvexnum,arcnum;/顶点数和边数/intkind;/图的类型/ADJGRAPH;举例说明:设有连通图如图71所示,顶点值设定为V1=100,V2=200,V3=300,V4=400,V5=500,V6=600,V7=700,V8=800,8个顶点和9条边的编号如图71所示。图7.1连通图数据输入过程如图72所示。图7.2数据输入输出结果如图73所示。l78数据结构习题解析与实训图7.3输出结果注意:此连通图邻接链表结构的建立过程是依赖于图7.1中8个顶点和9条边的编号。顶点和边的编号可以预先规定,编法不同,则数据输入的过程和输出的结果也会不同,但广度优先遍历算法的结果都是正确的。【解答】#includedatastru.h#include#includeADJGRAPHcreat_adjgraph()EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=2;printf(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放顶点数在adjg.vexnum中/adjg.arcnum=d;/存放边点数在adjg.arcnum中/printf(nn);for(i=0;iadjg.vexnum;i+)第7章图l79printf(输入顶点%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);/输入顶点的值/fflush(stdin);adjg.adjlisti.link=NULL;printf(nn);for(i=0;iadjg.arcnum;i+)printf(输入第%d条边的起始顶点和终止顶点(用逗号隔开):,i+1);scanf(%d,%d,&s,&d);/输入边的起始顶点和终止顶点/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(输入错,重新输入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/建立一个和边相关的结点/p-adjvex=d;p-next=adjg.adjlists.link;/挂到对应的单链表上/adjg.adjlists.link=p;p=malloc(sizeof(EDGENODE);/建立另一个和边相关的结点/p-adjvex=s;p-next=adjg.adjlistd.link;/挂到对应的单链表上/adjg.adjlistd.link=p;returnadjg;voidinitlinkqueue(LINKQUEUEq)/初始化广度优先遍历算法中用到的链队列/q-front=malloc(sizeof(LINKQLIST);(q-front)-next=NULL;q-rear=q-front;intemptylinkqueue(LINKQUEUEq)/判队空?/intv;if(q-front=q-rear)v=1;elsev=0;returnv;voidenlinkqueue(LINKQUEUEq,DATATYPE1x)/元素x入队列/l80数据结构习题解析与实训(q-rear)-next=malloc(sizeof(LINKQLIST);q-rear=(q-rear)-next;(q-rear)-data=x;(q-rear)-next=NULL;DATATYPE1dellinkqueue(LINKQUEUEq)/删除队头元素/LINKQLISTp;DATATYPE1v;if(emptylinkqueue(q)printf(队列空.n);v=0;elsep=(q-front)-next;(q-front)-next=p-next;if(p-next=NULL)q-rear=q-front;v=p-data;free(p);returnv;voidbfs(ADJGRAPHadjg,intvi)/连通图的广度优先遍历算法:从vi顶点出发/intvisitedMAXLEN;inti,v;EDGENODEp;LINKQUEUEque,q;q=&que;initlinkqueue(q);for(i=0;iadjvex=0)visitedp-adjvex=1;printf(%d,adjg.adjlistp-adjvex.vertex);第7章图l81enlinkqueue(q,(p-adjvex)+1);/遍历到的未访问过的结点编号入队列/p=p-next;main()ADJGRAPHag;intj;printf(n连通图的广度遍历n);ag=creat_adjgraph();/建立连通图的邻接链表结构/printf(nn输入广度优先遍历起始顶点(1%d):,ag.vexnum);scanf(%d,&j);printf(nn广度优先遍历结果序列:);bfs(ag,j);/连通图的广度遍历算法/printf(nn);【习题2】连通图上实现深度优先遍历题目要求:在以邻接链表为存储结构的无向图上,实现无向图深度优先遍历算法。结构说明:同上题。举例说明:数据输入过程及输出结果如图74所示。图7.4输入及输出l82数据结构习题解析与实训【解答】#include#includedatastru.h#includeintvisitedMAXLEN;ADJGRAPHcreat_adjgraph()EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=2;printf(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放顶点数在adjg.vexnum中/adjg.arcnum=d;/存放边点数在adjg.arcnum中/printf(nn);for(i=0;iadjg.vexnum;i+)/输入顶点的值/printf(输入顶点%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);fflush(stdin);adjg.adjlisti.link=NULL;printf(n);for(i=0;iadjg.arcnum;i+)printf(输入第%d条边的起始顶点和终止顶点(用逗号隔开):,i+1);scanf(%d,%d,&s,&d);/输入边的起始顶点和终止顶点/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(输入错,重新输入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/建立一个和边相关的结点/p-adjvex=d;p-next=adjg.adjlists.link;/挂到对应的单链表上/adjg.adjlists.link=p;p=malloc(sizeof(EDGENODE);/建立另一个和边相关的结点/p-adjvex=s;p-next=adjg.adjlistd.link;/挂到对应的单链表上/adjg.adjlistd.link=p;第7章图l83returnadjg;voiddfs(ADJGRAPHadjg,intv)/连通图的深度优先遍历算法:从v顶点出发/EDGENODEp;visitedv-1=1;/从编号为v的顶点出发,visited数组对应位置1/v-;printf(%d,adjg.adjlistv.vertex);/输出v顶点/p=adjg.adjlistv.link;/取单链表的第一个结点/while(p!=NULL)/对应单链表不空,进行遍历/f(visitedp-adjvex=0)/如果有未被访问过的结点/dfs(adjg,(p-adjvex)+1);/递归调用深度优先遍历算法/p=p-next;/取单链表的下一个结点/main()ADJGRAPHag;inti;printf(n连通图的深度遍历n);ag=creat_adjgraph();/建立连通图的邻接链表结构/for(i=0;iag.vexnum;i+)/visited数组初始化,均置0/visitedi=0;printf(nn输入深度优先遍历起始顶点(1-%d):,ag.vexnum);scanf(%d,&i);printf(nn深度优先遍历结果序列:);dfs(ag,i);/连通图的深度优先遍历算法/printf(nn);图7.5有向图1【习题3】拓扑排序题目要求:在以邻接链表为存储结构的有向图上,实现有向图的拓扑排序。结构说明:同上题。举例说明:设有向图如图75所示,顶点值设定为V1=100,V2=200,V3=300,V4=400,V5=500,V6=600,6个顶点和8条边的编号如图75所示。数据输入过程及输出结果如图76所示。l84数据结构习题解析与实训图7.6对应输入的结果【解答】#include#include#includedatastru.hADJGRAPHcreat_adjgraph()/建立有向图的邻接链表结构/EDGENODEp;inti,s,d;ADJGRAPHadjg;adjg.kind=1;printf(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/存放顶点数在adjg.vexnum中/adjg.arcnum=d;/存放边点数在adjg.arcnum中/printf(nn);for(i=0;iadjg.vexnum;i+)/邻接链表顶点初始化/printf(输入顶点%d的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);/输入顶点的值/第7章图l85fflush(stdin);adjg.adjlisti.link=NULL;adjg.adjlisti.id=0;printf(nn);for(i=0;iadjg.arcnum;i+)printf(输入第%d条有向弧的起始顶点和终止顶点(用逗号隔开):,i+1);scanf(%d,%d,&s,&d);/输入弧的起始顶点和终止顶点/fflush(stdin);while(sadjg.vexnum|dadjg.vexnum)printf(输入错,重新输入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/每条弧对应生成一个结点/p-adjvex=d;p-next=adjg.adjlists.link;/结点插入对应的单链表上/adjg.adjlists.link=p;adjg.adjlistd.id+;/弧的终端顶点入度加1/returnadjg;voidtopsort(ADJGRAPHag)inti,j,k,m,n,top;EDGENODEp;n=ag.vexnum;top=-1;/拓扑排序中用到的栈初始化/for(i=0;iadjvex;ag.adjlistk.id-;/删除相关的弧,即弧终点结点的入度减1/if(ag.adjlistk.id=0)/出现新的入度为0的顶点,将其入栈/g.adjlistk.id=top;top=k;p=p-next;if(mn)printf(nn有向图中有环路!nn);/拓扑排序过程中输出的顶点数小于有向图的顶点数/main()DJGRAPHag;printf(n有向图的拓扑排序n);ag=creat_adjgraph();/建立有向图的邻接链表结构/topsort(ag);/进行拓扑排序/printf(nn);【习题4】求最短路径题目要求:在以邻接矩阵为存储结构的有向图上,求单源点到其他顶点的最短路径。结构说明:#defineVEXTYPEint#defineADJTYPEint#defineMAXLEN40typedefstructotherdata;/图中边的信息,在下面的分析和讨论中忽略不考虑/VEXTYPEvexsMAXLEN;/图中顶点的信息/ADJTYPEarcsMAXLENMAXLEN;/邻接矩阵/intvexnum,arcnum;/顶点数和边数/intkind;/图的类型/MGRAPH;举例说明:设有向图如图77所示,顶点值设定为V1=100,V2=200,V3=300,V4=400,V5=500,V6=600,V7=700,7个顶点和11条边的编号如图77所示。数据输入过程如图78所示,输出结果如图79所示。第7章图l87图7.7有向图2图7.8输入图7.9结果l88数据结构习题解析与实训【解答】#includedatastru.h#include#include#defineMAX10000MGRAPHcreate_mgraph()/建立有向图的邻接矩阵结构/inti,j,k,h;MGRAPHmg;mg.kind=3;printf(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&i,&j);mg.vexnum=i;/存放顶点数在mg.vexnum中/mg.arcnum=j;/存放边点数在mg.arcnum中/fflush(stdin);for(i=0;img.vexnum;i+)printf(输入顶点%d的值:,i+1);/输入顶点的值/scanf(%d,&mg.vexsi);fflush(stdin);for(i=0;img.vexnum;i+)/邻接矩阵初始化/for(j=0;jmg.vexnum;j+)mg.arcsij=MAX;for(k=1;k=mg.arcnum;k+)printf(输入第%d条边的起始顶点和终止顶点(用逗号隔开):,k);scanf(%d,%d,&i,&j);/输入弧的起始顶点和终止顶点/fflush(stdin);while(img.vexnum|jmg.vexnum)printf(输入错,重新输入:);scanf(%d,%d,&i,&j);printf(输入此边权值:);/输入弧上之权值/scanf(%d,&h);mg.arcsi-1j-1=h;returnmg;main()MGRAPHmg;intcostMAXLENMAXLEN;第7章图l89intpathMAXLEN,sMAXLEN;intdistMAXLEN;inti,j,n,v0,min,u;printf(n求有向图单源点最短路径n);mg=create_mgraph();/建立有向图的邻接矩阵结构/printf(nn起始顶点为:);/有向图中顶点的编号从1编起/scanf(%d,&v0);v0-;n=mg.vexnum;for(i=0;in;i+)/cost矩阵初始化/for(j=0;jn;j+)costij=mg.arcsij;costii=0;for(i=0;in;i+)disti=costv0i;/dist数组初始化/if(disti0)/path数组初始化/pathi=v0;for(i=0;in;i+)/s数组初始化/si=0;sv0=1;for(i=0;in;i+)/按最短路径递增算法计算/min=MAX;u=v0;for(j=0;jn;j+)if(sj=0&distjmin)min=distj;u=j;su=1;/u顶点是求得最短路径的顶点编号/for(j=0;jn;j+)if(sj=0&distu+costujdistj)/调整dist/distj=distu+costuj;pathj=u;/path记录了路径经过的顶点/for(i=0;in;i+)/打印结果/if(si=1)u=i;while(u!=v0)printf(%d-,u+1);u=pathu;printf(%d,u+1);printf(d=%dn,disti);/有路径/l90数据结构习题解析与实训elseprintf(%d-%dd=MAXn,i+1,v0+1);/无路径/printf(nn);【习题5】图的邻接矩阵结构转为邻接链表结构题目要求:将连通图的邻接矩阵结构转为邻接链表结构。结构说明:图的邻接矩阵结构同【习题4】;图的邻接链表结构同【习题1】。举例说明:以【习题1】中的图71连通图为例,输出结果如图710所示。图7.10转变的结果【解答】#includedatastru.h#include#includeMGRAPHcreate_mgraph()/建立图的邻接矩阵/inti,j,k;MGRAPHmg;mg.kind=2;printf(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&i,&j);fflush(stdin);mg.vexnum=i;第7章图l91mg.arcnum=j;printf(nn);for(i=0;img.vexnum;i+)printf(输入顶点%d的值:,i+1);scanf(%d,&mg.vexsi);fflush(stdin);for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)mg.arcsij=0;for(k=1;k=mg.arcnum;k+)printf(输入第%d条边的起始顶点和终止顶点(用逗号隔开):,k);scanf(%d,%d,&i,&j);fflush(stdin);while(img.vexnum|jmg.vexnum)printf(输入错,重新输入:);scanf(%d,%d,&i,&j);mg.arcsi-1j-1=1;mg.arcsj-1i-1=1;returnmg;ADJGRAPHmg_to_adjg(MGRAPHmg)nti,j,n;ADJGRAPHadjg;EDGENODEp;n=mg.vexnum;adjg.vexnum=mg.vexnum;