数据结构图的操作.docx

实验7:图的操作算法一、实验目的1 .熟悉各种图的存储结构。2 .掌握图的各种搜索路径的遍历方法。二、实验内容L设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。算法：#include<iostream>#include<math.h>#include<stdio.h>#include<malloc.h>#defineMAXV10#defineINF980708usingnamespacestd;typedefintInfoType;邻接矩阵typedefstruct（intno;InfoTypeinfo;JVertexType;顶点类型typedefstruct（intedgesMAXVMAXV;intnze;VertexTypeve×sMAXV;MatGraph;完整的图邻接矩阵类型邻接表typedefstructANode（intadjve×structANode*nextarc;intweight;ArCNOde;边结点类型typedefstructVnodeInfoTypeinfo;ArcNode*firstarc;VNode;邻接表的头结点类型typedefstruct(VNodeadjlistMAXV;intn,e;AdjGraph;完整的图邻接表类型typedefstruct(InfoTypedataMAXV;intfront,rear;SqQueue;队列初始化队列voidInitQUeUe(SqQUeUe*&q)(q=(SqQueue*)malloc(sizeof(SqQueue);q->front=q->rear=-l;)判断队列是否为空boolQueueEmptyfSqQueue*q)(return(q->front=q->rear);)进队列booleQueue(SqQueue*&q,InfoTypee)(if(q->rear=MAXV)returnfalse;q->rear+;q->dataq->rear=e;returntrue;)出队列booldeQueue(SqQueue*&q,InfoType&e)(if(q->front=q->rear)returnfalse;q->front=(q->front+l)%MAXV;e=q->dataq->front;returntrue;)创建邻接表voidCreateAdj(AdjGraph*&GJntAMAXVMAXVJntnjnte)(intij;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph);for(i=0;i<n;i+)G->adjlisti.firstarc=NULL;for(i=0;i<n;i+)for(j=n-lj>=OJ-)if(Aij!=O&&Ai0!=INF)p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=j;p->nextarc=G->adjIisti.firstarc;G->adjlisti.firstarc=p;)G->n=n;G->e=e;)输出邻接表voidDispAdj(AdjGraph*G)(COUt<<“邻接表存储："<<endl;inti;ArcNode*p;for(i=0;i<G->n;i+)(p=G->adjlisti.firstarc;printf("%3d"zi);printf("%3d->,J);while(p!=NULL)(printf("%3d->,p->adjvex);p=p->nextarc;)cout«"A"«endl;)/DFS深度优先遍历intvisitedMAXV=0;voidDFSfAdjGraph*G,intv)(ArcNode*p;visitedv=l;cout<<v;p=G->adjlistv.firstarc;while(p!=NULL)(if(visitedp->adjvex=O)DFS(G,p->adjvex);p=p->nextarc;)/BFS广度优先遍历voidBFS(AdjGraph*GJntv)(intWjjArcNode*p;SqQueue*qu;InitQueue(qu);intvisitedlMAXV;for(inti=0;i<G->n;i+)visitedli=O;printf("%2d',v);visitedlv=l;enQueue(qu,v);while(!QueueEmpty(qu)(deQueue(quzw);p=G->adjlistw.firstarc;while(p!=NULL)(if(visitedlp->adjvex=O)(printf("%2d",p->adjvex);visitedlp->adjvex=l;eQueue(qu,p->adjvex);p=p->nextarc;)cout<<endl;)销毁邻接表voidDestroyAdj(AdjGraph*&G)(inti;ArcNode*pre,*p;for(i=0;i<G->n;i+)(pre=G->adjlisti.firstarc;if(pre!=NULL)(p=pre->nextarc;while(p!=NULL)(free(pre);pre=p;p=p->nextarc;free(pre);)free(G);)创建邻接矩阵voidCreatMat(MatGraph*&GJntnjnte)(intijljjlznuml,num2;G=(MatGraph*)malloc(sizeof(MatGraph);邻接矩阵初始化for(i=0;i<n;i+)(for(j=0;j<n;j+)G->edgesij=O;)顶点信息COUt<<"请输入顶点编号"<<endl;for(i=0;i<n;i+)cin>>G->vexsi.no;边信息for(i=0;i<e;i+)(COUt<<”请输入起始端点编号和终止端点编号*<endl;cin>>il>>jl;for(j=0;j<n;j+)(if(G->vexsj.no=il)numl=j;if(G->vexsj.no=jl)num2=j;)G->edgesnumlnum2=l;)G->n=n;G->e=e;)输出邻接矩阵voidDispMat(MatGraph*G)(cout<<”邻接矩阵存储："<<endl;cout<<"tt"for(inti=0;i<G->n;i+)cout<<G->vexsi.no<<"t"cout<<endl;for(inti=0;i<G->n;i+)(cout<<"t"<<G->vexsi.no<<"t"for(intj=O;j<G->n;j+)cout<<G->edgesij<<"t"cout<<endl;)intmain()(intnze,½vl;MatGraph*G;AdjGraph*p;COUt<<"请输入顶点个数"<<endl;cin>>n;COUt<<"请输入边的个数"<<endl;cin>>e;CreatMat(G,nze);DispMat(G);CreateAdj(p,G->edges,nze);DispAdj(p);COUt<<"进行DFS深度优先遍历，请输入初始点：cin>>v;DFS(pzv);cout<<endl;COUt<<"进行BFS广度优先遍历，请输入初始点：cin>>vl;BFS(p,vl);COUt<<"销毁图"<<endl;DestroyAdj(p);)测试数据:有向图：无向图:12345101110200010300001400100501000邻接表存储：0:0->IE ->2->3->'1:13运行结果:请输入顶点个数3输入边的个数1输入顶点编号12345请输入起始端点编号和终止端点编号13请输入起始端点编号和终止端点编号14请输入起始端点编号和终止端点编号12请输入起始端点编号和终止端点编号43请输入起始端点编号和终止端点编号2 4请输入起始端点编号和终止端点编号3 5请输入起始端点编号和终止端点编号5 2邻接矩阵存储：2->3->请输入初始点：1请输入初始点：1>>>>>,-STJTJ-IJnJTJLLLLL1342It>>>>>t:-S/(mlIi-J深1o1234S接O.1:2:3:4:F4存在问题：无2.求两点之间最短路径。算法设计：求两点之间最短路径。#include<iostream>#include<math.h>#include<stdio.h>#include<malloc.h>#defineINF32767#defineMAXVIOOusingnamespacestd;typedefcharInfoType;以下定义邻接矩阵类型typedefstructintno;顶点编号InfoTypeinfo;顶点其他信息VertexType;typedefstruct顶点类型intedgesMAXVMAXV;邻接矩阵数组intnze;顶点数，边数VertexTypevexsMAXV;存放顶点信息MatGraph;完整的图邻接矩阵类型voidCreateMat(MatGraph&g,intAMAXVMAXVJntnjnte)仓IJ建图的邻接矩阵inti,j;g.n=n;g.e=e;for(i=0;i<g,n;i+)for(j=O;j<g.n;j+)g.edgesij=Aij;voidDispMat(MatGraphg)输出邻接矩阵ginti,j;for(i=0;i<g,n;i+)for(j=O;j<g,n;j+)if(g.edgesij!=INF)printf("%4d,g.edgesij);elseprintf("%4s"z"");cout<<endl;)voidDispath(MatGraphg,intdistzintpathJntSJntv)输出从顶点v出发的所有最短路径inti,j,k;intapathMAXVzd;存放一条最短路径(逆向)及其顶点个数for(i=0;i<g.n;i+)循环输出从顶点V到i的路径if(Si=l&&i!=v)cout<<,'从顶点,<<v<<"到顶点"<<iv<”的路径长度为:',<<disti<v"路径为:"d=0;apathd=i;添加路径上的终点k=pathi;if(k=-l)没有路径的情况COUt<<"无路径"<<endl;else存在路径时输出该路径while(k!=v)d+;apathd=k;k=pathk;)d+;apathd=v;添加路径上的起点cout<<apathd;先输出起点for(j=d-l;j>=O;j-)再输出其他顶点cout<<",<<apathj;cout<<endl;顶点V到顶点i没边时，置顶点i的前一个顶点为-1)voidDijkstrafMatGraphg,intv)/Dijkstra算法intdistMAXVzpathMAXV;intSMAXV;/Si=l表示顶点i在S中,Si=0表示顶点i在U中intMindisJJzu;for(i=O;i<g.n;i+)disti=g.edgesvi;距离初始化Si=0;S置空if(g.edgesvi<INF)路径初始化pathi=v;顶点V到顶点i有边时，置顶点i的前一个顶点为Velsepathi=-l;Sv=l;pathv=O;源点编号V放入S中for(i=0;i<g.n-l;i+)循环直到所有顶点的最短路径都求出Mindis=INF;/Mindis置最大长度初值for(j=OJ<g.nj+)选取不在S中(即U中)且具有最小最短路径长度的顶点uif(Sj=O&&distj<Mindis)u=j;Mindis=distj;Su=l;顶点u加入S中for(j=O;j<g.n;j+)修改不在S中(即U中)的顶点的最短路径if(SUl=O)if(g.edgesuj<INF&&distu+g.edgesuj<distj)distj=distu+g.edgesuj;pathj=u;)DiSPath(g,dist,path,S,v);输出最短路径intmain()(MatGraphg;intAMAXVMAXV=0,4,INFJNF,INF,0,1,INF,4,INF,0,2,3JNFJNFz0);intn=4,e=8;CreateMat(gzA,n,e);建立教程中图835的邻接矩阵COUt<<”图G的邻接矩阵:"<<endl;DispMat(g);输出邻接矩阵intv;CoUt<<"输入一顶点:"<<endl;cin>>v;CoIlt<<"从"<<v<<"顶点出发的最短路径如下:"<<enc;Dijkstra(g,v);测试数据:图:运行结果:,200:勺勺勺DT度度度05012的点点点g啜顶顶出到到到333占g八点点IklIATIf存在问题：无3、实现一个有向图的拓扑排序。算法设计：#include<iostream>#include<math.h>#include<stdio.h>#include<malloc.h>#defineMAXV10#defineINF980708usingnamespacestd;typedefintInfoType;邻接矩阵typedefstruct(intno;InfoTypeinfo;Verte×Type;顶点类型typedefstruct(intedgesMAXVMAXV;intn,e;VertexTypevexsMAXV;MatGraph;完整的图邻接矩阵类型邻接表typedefstructANode(intadjvex;structANode*nextarc;intweight;ArcNode;边结点类型typedefstructVnode(InfoTypeinfo;intcount;ArcNode*firstarc;VNode;邻接表的头结点类型typedefstruct(VNodeadjlistMAXV;intn,e;AdjGraph;完整的图邻接表类型创建邻接表voidCreateAdjfAdjGraph*&GJntAMAXVMAXVJntn,inte)(intij；ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph);for(i=0;i<n;i+)G->adjlisti.firstarc=NULL;for(i=0;i<n;i+)for(j=n-l;j>=0;j-)if(AiU!=O&&Ai0>=INF)(p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=j;p->nextarc=G->adjlisti.firstarc;G->adjlisti.firstarc=p;)G->n=n;G->e=e;)输出邻接表voidDispAdj(AdjGraph*G)(COUtV<”邻接表存储:"<<endl;inti;ArcNode*p;for(i=0;i<G->n;i+)(p=G->adjlisti.firstarc;pntf("%3d'J);printf("%3d->"J);while(p!=NULL)(printf("%3d->",p->adjvex);p=p->nextarc;)cout«"A"«endl;)销毁邻接表voidDestroyAdj(AdjGraph*&G)inti;ArcNode*pre,*p;for(i=0;i<G->n;i+)(pre=G->adjlisti.firstarc;if(pre!=NULL)(p=pre->nextarc;while(p!=NULL)(free(pre);pre=p;p=p->nextarc;)free(pre);)free(G);)创建邻接矩阵voidCreatMatlMatGraph*&GJntn,inte)(intiziljjlznuml,num2;G=(MatGraph*)malloc(sizeof(MatGraph);邻接矩阵初始化for(i=0;i<n;i+)(for(j=0;j<n;j+)G->edgesij=O;)顶点信息cout<<”请输入顶点编号”<<endl;for(i=0;i<n;i+)cin>>G->vexsi.no;边信息for(i=0;i<e;i+)(COUt<<"请输入起始端点编号和终止端点编号"<<endl;cin>>il>>jl;for(j=0;j<n;j+)(if(G->vexsj.no=il)numl=j;if(G->vexsj.no=jl)num2=j;)G->edgesnumlnum2=l;)G->n=n;G->e=e;)拓扑排序算法voidTopSort(AdjGraph*G)拓扑排序算法iti,j；intStMAXV,top=-l;栈St的指针为topArcNode*p;for(i=O;i<G->n;i+)入度置初值OG->adjlisti.count=0;for(i=O;i<G->n;i+)求所有顶点的入度G->adjlistp->adjvex.count+;p=p->nextarc;p=G->adjlisti.firstarc;while(p!=NULL)将入度为O的顶点进栈)for(i=O;i<G->n;i+)if(G->adjlisti.count=0)top+;Sttop=i;)while (top>-l)i=Sttop;top-;printf("%d "J);p=G->adjlisti.firstarc; while (p!=NULL)栈不空循环出栈一个顶点i输出该顶点找第一个邻接点将顶点i的出边邻接点的入度减1j=p->adjvex;G->adjlistj.count-;if(G->adjlistj.count=0) 将入度为O的邻接点进栈 top+；Sttop=j;)p=p->nextarc;)intmain()找下一个邻接点intn,e,v,vl;MatGraph *G;AdjGraph *p;CoUt<<"请输入顶点个数" <<endl;cin>>n;CoUt<<"请输入边的个数" <<endl;cin>>e;CreatMat(Gzn,e);CreateAdj(P,G->edges,n,e);CoUt<< “邻接表" <<endl;DispAdj(p);Cout<<"拓扑排序序列"<<endl;TopSortfp);)测试数据:有向图:运行结果:国输入顶点编号012345演输入起立年喈点编号和终止端点编号N褊入起始端点编号和终止端点编号W输入起始造点编号和终止端点编号信输入起始端点编号和终止端点编号4 1惘输入起始端点编号和终止端点编号旖输入起始端点编号和终止端点编号5 3一软翼重存储：0:01->1Cl->1=1E1->2CJ->2：2E3->3(>人3：3C一）公44C->1CJ->!5C3->55t1->3CJ->拓扑排序序列存在问题：无三、本次实验问题分析及学习建议本次学习图的知识，从“一对一”的线性表到“一对多”的数，到现在的“多对多”的图，感觉越来越困难。代码量大还多，感觉需要掌握和记得东西很多，学起来很吃力。备注：1 .每次实验完毕，各位学生可提交实验报告纸质（A4打印）及实验源程序代码,命名格式为学号J名_sy序号题号.cpp",若多个文件则以文件夹"学号J名_sy序号保存。以实验一为例子：17000001_李四cpp,17000OOL李四_syl_2.cpp,170000OL李四_syl_4.cpp,可保存为“170000OL李四_syl”文件夹。2 .每次实验项目提交，请依据教师提供实验项目卡复制填写实验目的及实验内容，算法设计及测试运行结果、存在问题分析等以实际填写。