实验四--图的操作及应用

1实验四图的操作及应用实验课程名：数据结构与算法一、实验目的及要求1、理解图的基本概念及术语。2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。3、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列。二、实验内容任务一：构造如图1所示的图的邻接矩阵存储结构和邻接表存储结构。图1解答：（1）源代码：#includeiostream.h#includemalloc.h#includeconio.h#defineINFINITY1000#defineMAX_VERTEX_NUM20#defineOK1#defineSTARTS********************************typedefenum{DG,DN,UDG,UDN}GraphKind;typedefintEType;typedefintInfoType;typedefintVertexType;typedefstructArcCell//definestructureMGraph{ETypeadj;InfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];2AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;}MGraph;intCreatUDN(MGraph&G)//CreatUDN()sub-function{intIncInfo,i,j,k,v1,v2,w;coutendlPleaseinputthenumberofG.vexnum(eg,G.vexnum=4):;cinG.vexnum;//inputthenumberofvexcoutPleaseinputthenumberofG.arcnum(eg,G.arcnum=4):;cinG.arcnum;//inputthenumberofarccoutPleaseinputIncInfo(0fornone):;cinIncInfo;for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j){G.arcs[i][j].adj=INFINITY;//initialG.arcs[i][j].adjG.arcs[i][j].info=NULL;//initialG.arcs[i][j].info}coutPleseinputarc(V1--V2),Forexample:(V1=1,V2=3),(V1=2,V2=4)...endl;for(k=0;kG.arcnum;++k)//inputarc(v1,v2){coutendlPleaseinputthek+1tharc'sv1(0v1G.vexnum):;cinv1;//inputv1coutPleaseinputthek+1tharc'sv2(0v2G.vexnum):;cinv2;//inputv2coutPleaseinputthek+1tharc'sweight:;cinw;//inputweighti=v1;j=v2;while(i1||iG.vexnum||j1||jG.vexnum)//if(v1,v2)illegal,again{3coutPleaseinputthek+1tharc'sv1(0v1G.vexnum):;cinv1;coutPleaseinputthek+1tharc'sv2(0v1G.vexnum):;cinv2;coutPleaseinputthek+1tharc'sweight:;cinw;i=v1;j=v2;}//whileendi--;j--;G.arcs[i][j].adj=G.arcs[j][i].adj=w;//weightcoutG.arcs[i+1][j+1].adj=G.arcs[j+1][i+1].adj=wendl;if(IncInfo){coutPleaseinputthek+1tharc'sInfo:;cin*G.arcs[i][j].info;}}//forendreturn(OK);}//CreatUDN()endvoidGprintf(MGraphG)//打印邻接矩阵{cout邻接矩阵数组为：\n;for(inti=0;iG.vexnum;i++){for(intk=0;kG.vexnum;k++)coutG.arcs[i][k].adj\t;coutendl;}}/*邻接表*/typedefstructArcNode//definestructureALGraph{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstructVNode4{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intCreateDG(ALGraph&G)//CreateDG()subfunction{intIncInfo,i,j,k,v1,v2,w;coutendlPleaseinputthenumberofG.vexnum(eg,G.vexnum=4):;cinG.vexnum;//inputthenumberofvexcoutPleaseinputthenumberofG.arcnum(eg,G.arcnum=4):;cinG.arcnum;//inputthenumbeofarccoutPleaseinputthenumberofIncInfo(0fornone):;cinIncInfo;//ifnoinformation,input0for(i=0;iG.vexnum;++i){G.vertices[i].data=i;//initialG.vertices[i].dataG.vertices[i].firstarc=NULL;//initialG.vertices[i].firstarc}coutPleseinputarc(V1--V2),Forexample:(V1=1,V2=3),(V1=2,V2=4)...endl;for(k=0;kG.arcnum;++k)//inputarc(v1,v2){coutendlPleaseinputthek+1tharc'sv1(0v1G.vexnum):;cinv1;coutPleaseinputthek+1tharc'sv2(0v2G.vexnum):;cinv2;i=v1;j=v2;while(i1||iG.vexnum||j1||jG.vexnum)//if(v1,v2)illegal{coutendlPleaseinputthek+1tharc'sv1(0v1G.vexnum):;cinv1;5coutPleaseinputthek+1tharc'sv2(0v2G.vexnum):;cinv2;i=v1;j=v2;}//whileendi--;j--;ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));//allocatememoryif(!p){coutOverflow!;return(0);}p-adjvex=j;//assignp-adjvexp-nextarc=G.vertices[i].firstarc;p-info=NULL;G.vertices[i].firstarc=p;if(IncInfo){coutPleaseinputtheinfo:;cin*(p-info);//inputinformation}}//forendreturn(OK);}//CreateDG()endintmain(){MGraphMG;ALGraphAG;inta=-1;while(a!=0){coutSTARTSSTARTSendl;cout(1)邻接矩阵(无向网)\t(2)邻接表(有向图)\t(3)退出endl;cout选择存储方式:;cina;switch(a){case1:{CreatUDN(MG);Gprintf(MG);break;}case2:CreateDG(AG);break;6case3:a=0;break;default:cout选择错误\nendl;}}return0;}（2）运行结果：7（3）运行结果分析：运用数组与链表的结合来实现任务二：用邻接表的存储结构创建一个如图2所示的图a，分别打印出这两个图的深度优先遍历和广度优先遍历的结点信息序列。图20165948372(a)603451278(b)8解答：（1）源代码：#includeiostream#includestring#includequeueusingnamespacestd;#defineERROR1#defineMAX_VERTEX_NUM100typedefstructArcNode{intadjvex;structArcNode*nextarc;stringinfo;}ArcNode;typedefstructVNode{chardate;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//当前图的vexnum顶点数和arcnum弧数intkind;}ALGraph;intLocateVex(ALGraph&G,char&v1){inti;for(i=0;iG.vexnum;i++){if(G.vertices[i].date==v1)returni;}if(i=G.vexnum)returnERROR;elsereturn0;}voidCreateDG(ALGraph&G){ArcNode*p,*q;charv1,v2;charv;inti,j,k,n;cout请输入图的顶点数和弧数：endl;cinG.vexnum;9cinG.arcnum;cout请输入顶点：endl;for(i=0;iG.vexnum;i++){cinv;G.vertices[i].date=v;G.vertices[i].firstarc=NULL;}cout请输入弧尾和弧头：;for(k=0;kG.arcnum;k++){cinv1;cinv2;i=LocateVex(G,v1);j=LocateVex(G,v2);if(G.vertices[i].firstarc==NULL){p=(ArcNode*)newArcNode;G.vertices[i].firstarc=p;q=G.vertices[i].firstarc;}else{q=G.vertices[i].firstarc;for(n=0;nG.arcnum;n++,q=q-nextarc){if(!q-nextarc)break;}p=(ArcNode*)newArcNode;q-nextarc=p;q=q-nextarc