数据结构实验图的邻接表和邻接矩阵操作

《数据结构实验图的邻接表和邻接矩阵操作》由会员分享，可在线阅读，更多相关《数据结构实验图的邻接表和邻接矩阵操作（30页珍藏版）》请在装配图网上搜索。

1、实验报告6课程数据结构实验名称图的建立及遍历专业班级学号姓名实验日期：2010年11月23日第页评分1. 学会用邻接矩阵和邻接表实现图结构和刘图的基本操作。2. 掌握对图操作的具体实现；3. 掌握图的两种遍历算法（深度优先、广度优先）；4. 掌握求图的最小生成树和顶点间最短路径的算法：1、建立图的邻接表存储结构，并基于邻接表结构，完成以下实验内容。2、深度优先遍历，显示遍历结果。3、用Prim法求连通图的最小生成树4、用Dijkstra算法求某一确定顶点到所有其它顶点的最短路径。四、实验步骤(描述实验步骤及中间的结杲或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果)1. 本实验中的

2、函数有：StatusCreateGraph(ALGraph&G)StatusOutPut(mtv)StatusCreateUDG(ALGiaph&G)StatusCreateUDN(ALGraph&G)StatusCreateDG(ALGraph&G)StatusCreateDN(ALGiaph&G)StatusFnstAdjex(ALGraphG,intv)StatusNextAdjAex(ALGraphG,mtv?mtw)StatusLocatedex(ALGiaphG,VertexTypev)mtminmium(MmiSpanTree_FlagFlag社intn)voidMiniSpan

3、Tree_PRIM(ALGraphG,VeitexTypev)voidShortestPath_DIJ(ALGraphG,mtvOPathMatnx&RShortPatliTable&D)voidBFSTraverse(ALGiaphG,Status(*visit)(mtv)voidDFS(ALGraphG,mtv)voidDFSTraverse(ALGraphG,Status(*visit)(intv)2. 完整代码如下：/daUstruct图邻接表基本操作#include# mclude# mclude11#include#include#includeusmgnamespacestd;#

4、defineOK1#defineERROR0#defineTRUE1#defineNOTFOUND-1#defineFALSE0#defineOATRFLOW-2#defineINFINITYINT_MAX#defineMAX_TX_NUM20#defineINFO_LENGTH10typedefmtStatus;typedefmtAirType;typedefchai*InfoTypey/10typedefcharVertexType10j;（?02任叽缶）2，14疗曲血心/侑向图，有向网，无向图，无向网mtvisitedMtypedefenumtypedefstrukMNttdT二/弧的结

5、点类型mtadjvex;该弧指向的顶点的位置ArcTypeweight;stnictAicNode*nextarc;/指向下一条弧指针/Infoiype*info；该弧相关信息的指针AicNode;typedefstnictNodeVertexTypedata;顶点信息AicNode*firstarc;指向第一条依附该顶点的弧的指针NbodeAdjListOlAXVEXNUNI;typedefstnictAdjListvertices;mtvexiium,arcnum;GrapliKindkind;ALGraph;ALGraphG;stnictMnuSpanTree_FlagPrtexType

6、adjvex;ArcTypelowcost;closedgeMAX_TX_NUM;typedefboolPathNIatnxMAX_TX_NUMMAX_TX_NUM;typedefmtShortPathTableNIAX_TX_NUM;StatusOutPut(mtv)pnntf(,%10s,G.veiticesv.data);retiiniOK;StatusLocatedex(ALGraphG,*VertexTypev)mti=0;while(sti-cmp(G.verticesi.data?v)!=O)i-H-;if(i=G.vexiium)return-1;retiinii;Status

7、CreateD1/W向图mtweight;AicNode*p;prmtf(输入顶点数和弧数：n);scaiif(M%d%d,&G.vexiium,&G.arcnum);pnntf(M请输入1个顶点：nH,G.vexiium);fdr(i=O;iG.verticesidata);构造顶点向量G.verticesi.fii-starc=NULL;PrtexTypevw；prmtf(请输入d条弧，vl-v2则输入vlv2w(无权图w为1,有权图，w为权值)nM,G.arcnum);for(k=0;kw?&weight);w=LocateVex(G,v);ww=LocatePx(G,w);p=(Ai-

8、cNode*)malloc(sizeof(Ai-cNode);padjvex=ww;p-weight=weight;p-nextarc=G.verticesw.fii-starc;G.verticesw.fiistarc=p;returnOK;StatusCreateDN(ALGraph&G)/W向网intikwN,weight;AicNode*p;pnntf(输入顶点数和弧数：n”)；scaiif(M%d%d,&G.vexiium,&G.arcnum);pnntf(M请输入1个顶点：n*G.vexiium);fdr(i=O;iG.vexnum;i+)scanf(,%s,G.verticesi

9、data);构造顶点向量G.verticesi.fii-starc=NULL;PrtexType;w；nM,G.arcnum);for(k=0;kv2则输入vlv2w（无权图w为1,有权图，w为权值）scaiif(M%s%s%d,v,w?&weight);ocateexfpvXww=Lo&虑理上亠亠薛还如oc(sizeof(ArcNode);/q=(ArcNode*)maIloc(sizeof(ArcNode);padjvex=ww;p-weight=weight;p-nextarc=G.verticesw.fii-starc;G.verticesw.firstarc=p;retimiOK;S

10、tatusCreateUDG(ALGiaph&G)/无向图mti,weight;VertexTypev,w;mtwvw;位置AicNode*p,*q；printf(”请输入顶点数和弧数:n);scaiif(H%d%d,&G.vexiium&G.arcnum);pnntf(H请输入1个顶点：n*G.vexiium);fdr(i=O;iG.vexnum;i+)scanf(,%s,G.verticesidata);G.verticesi.fii-starc=NULL;pnntf(请输入d对顶点关系，格式为vvw(若是无权图，w输入1,若是有权图，则w输入权)：nn,G.arcnum);for(i=0

11、;iw?&weight);w=LocateVex(G,v);ww=LocateVex(G，w);p=(Ai*cNode*)malloc(sizeof(AicNode);p-adjvex=vrw;p-weight=weight;p-nextarc=G.verticesw.fii-starc;G.verticesw.firstarc=p;strcmp(G.verticesw.data,v);q=(Ai*cNode*)malloc(sizeof(AicNode);qadjvex=w;q-weight=weight;q-nextarc=G.vertices,rw.firstarciG.vertices

12、v,firstaic=q;厂Cst严甲(G.诧rt誉龙retimiOK;StatusCreateUDN(ALGi-aph&G)无向网inti,weight;VertexTypev?w;mtw,ww;位置AicNode*p5*q;printf(请输入顶点数和弧数:n);scaiif(H%d%d,&G.vexiium&G.arcnum);pnntf(H请输入1个顶点：n*G.vexiium);fdr(i=O;iG.vexnum;i+)scaiif(M%s,G.verticesi.data);G.verticesi.fii-starc=NULL;prmtf(请输入d对顶点关系，格式为vvw(若是无权

13、图，w输入1,若是有权图，则w输入权)：nn,G.arcnum);fdr(i=0;iadjvex=vrw;p-weight=weight;p-nextarc=G.verticesw.fii-starc;G.verticesw.fiistarc=p;strcmp(G.verticesw.data,v);q=(Ai*cNode*)malloc(sizeof(AicNode);qadjvex=w;retimiq-weight=weight;q-nextarc=G.verticesArw.firstarc;G.verticesv,firstarc=q;strcmp(G.verticesvw.data,

14、w);StatusCreatGihtAt(j!)h&G)采用邻接矩阵表示法构造图G/chark3;prmtf(”请输入图的类型，输入数字(DG为0,DN为1,UDG为2,UDN为3)：n);scaiif(”&：&G.kin(i);switch(G.kmd)caseDG:pnntf(叫ttt创建有向图n”);CreateDG(G);returnOK;caseDN:pnntf(叫ttt创建有向网n”);CreateDN(G);returnOK;caseUDG:pnntf(叫ttt创建无向图n”);CreateUDG(G);returnOK;caseUDN:pnntf(叫ttt创建无向网n”);Cr

15、eateUDN(G);returnOK;default:retumERROR;voidPiintGraph(ALGraphG)7mti;AicNode*p;pnntf(M%6s%8s%12snM,”编号”顶点”相邻边编号”);fbr(i=O;inextarc)pnntf(H%4dM,p-adjvex);pniitf(HnH);StatusFustAdjex(ALGraphG,mtv)/参数是邻接表及要査找第一个邻接点的元素的位置if(G.veilicesv.fii-staic!=NULL)returnG.verticesv.fiistarc-retimiStatusNextAdjex(ALGr

16、aphG,intv,mtw)参数是邻接表及要査找下一个邻接点(相对)的元素的位置AicNode*p;p=G.verticesvfii-starc;while(p&p-adjvex!=v)p=p-nextarc;if(!p|!p-nextaic)retum-1;retimip-nextaic-adjvex;voidBFSTraverse(ALGraphG,Status(*visit)(intv)printf(”广度优先遍历结果：q);inti,j；mexnsetCvisited.falsesizeofvisited);dequedq;for(i=0;iu);j=O;j=NextAdjex(G,u

17、j)if(!visited|j)visitedj=tiiie;visit。)；dq.push_back(j);/*/voidDFS(ALGraphG,mtv)mtw;visitedv=tme;OutPiit(v);fdr(w=FirstAdjex(G,v);w=0;w=NextAdjrex(G,v?w)if(!visitedw)VOliDFS(Gw);idDFSTraveneCALGtajbhdSteM?(昨isit)(mtv)fd一pnntf（深度优先遍历结果如下n）;mtv;memsetCvisited.false.sizeofvisited);fdr(v=O;vVG.vexnuni;v+

18、)if(!visitedv)DFS(G,v);mtminmium(MmiSpanTree_FlagFlagjntn)mtmm=99999,pl1;fdr(inti=0;in;i+)if(Flagilowcost!=0&Flagi.lowcostmin)min=Flagilowcost;pl=i;9Iretiuiipl;voidMiniSpanTree_PRIM(ALGraphG,ertexTypev)AicNode*ptr;mti,k;k=Locateex(G,v);fdr(i=O:iadjvex.lowcost=ptr-weight;strcpy(closedgeptr-adjvex.adj

19、vex,v);pti-=ptr-nextarc;closedgek.lowcost=0;fdr(i=l;iweightadjvex.lowcost)closedgepti-adjvex.lowcost=ptr-weiglit;strcpy(closedgepti-adjvex.adjvex,G.verticesk.data);pti=ptr-iiextarc;voidShortestPath_DIJ(ALGraphG,mtvO.PathMatnx&PShortPatliTable&D)mti,v,w,k=vO;boolfinalNIAX_ATX_NUM;AicNode*ptr;for(i=0:

20、iG.vexnum;i+)/H个数组初始化finali=false;Di=INFINITY;for(v=0;vadjvex=ptr-weight;Pptr-adjvexvO=true;Pptr-adjvexptr-adjvex=true;pti-=ptr-nextarc;Dv0=0;finalO=true;Pv0v0=true;fdr(i=l;iG.vexnum;i+)mtmui=INFINITY;fbrii=O;vnextarc)if(Dk-rptr-weiglitadjvex)Dptr-adjvex=Dk+ptr-weight;fbr(v=O;wvG.vexnum;w+)Pptr-adjv

21、exw=Pkw;Pptr-adjvexpti-adjvex=tnie;pnntf(ndijkstia算法求出s到各顶点的最短距离如下：n,G.veiticesvO.data);fdr(i=O;i0&Div2则输入u2w（无权图初为ia0有权图轄为权.值）I:Iu2Iv4:v2!u3!u5:u3:u5i编号30顶点U1u2虫vS相邻边编号4252广度优先遍历结果，V0v4v2v5深度优先遍历结果如下u0u4u5u3请洞人最短路徑的起始点:M算法菇出UP到各顶点的最珂巨离如下!NONENONE10503012130121六、总结30121（说明实验过程中遇到的问题及解决办法；新发现或个人的收获；未

22、解决/需进一步研讨的问题或建议新实验方法等）1. 在对邻接矩阵获临界表的权作初值时，要用到“无穷”，所以：若要使用#defineINFINITYINT_MAX中的INFINITY,就要添加头文件#mclude,这样，无穷值就是mt类型的最大值2. 字符数组与字符数组之间复制用strcpy3. 邻接表的深度优先搜索以及广度优先搜索与输入关系的顺序有关，这是因为先输入哪个便先建立哪个，后建立的则接在最后一个节点的后面。七、思考与提高如果用邻接矩阵存储结构，如何实现上述的实验内容?完整代码如下：/datartruct图邻接矩阵基本操作没有弧信息时可以正确运行，有弧信息，在插入顶点时运行出错# inc

23、lude# include# include# include# include# includeusingnamespacestd;井defineOKIJdefineERROR)乙亠亠“亠井defineTRUeSh/亠亠井defineFALSE0井defineNOTFOUND井defineOVERFLOW-2井defineINFINITYINT_MAX/defineMAX_VERTEX_NUM20井defineINFO_LENGTH10typedefintStatus;typedefintVRType;typedefcharInfoType;typedefcharVertexType10;t

24、ypedefenumDG,DN,UDG,UDNGraphKind;有向图，有向网，无向图，无向网typedefstructArcCellVRTypeadj;/VRType是顶点关系类型，对于无权图，用丄或0表示相邻否：对带权图，则为权值类型InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrix(MAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/点向量AdjMatrixarcs;/邻接矩阵intvexnumzarcnum;图的当前顶点数和弧数GraphKindkind;/图的

25、种类标志MGraph;structMiniSpanTreeflagVertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;MGraphG;typedefboolPathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefintShortPathTableMAX_VERTEX_NUM;boolvisitedMAX_VERTEX_NUM;StatusOutputintv)printf(”5s舄G.vgxsM);returnOK;IintLocateVexCyuyaphGVertexJype):/在G中寻氟滙_亠亠“

26、inti;*、Ofor(i=0;iG.vexnum;i+)if(strcmp(G.vexsi/v)=O)break;returni;StatusCreateUDN(MGraph&G)构造无向网intijk,Incinfo,w;VertexTypevlzv2;printf(“请输入顶点数和弧数和弧的信息(0表示弧不包含其他信息，1表示弧含其他信息：n);scanf,%d%d%d,/&G.vexnum/&G.arcnum/&nclnfo);printf(”请输入d个顶点：XnG.vexnum);fori=0;iG.vexnum;i+)scanf(,%s,/&G.vexsi);for(i=0;iG.

27、vexnum;i+)/J始化矩阵for(j=0;jG.vexnum;j+)G.arcsij.adj=INFINITY;printf(请输入d对顶点关系，格式为vvw(若是无权图，w输入1,若是有权图，则w输入权):XnG.arcnum);fork=0;kG.arcnum;k+)scanf(,%s%s%d,/vl/v2,&w);i=LocateVex(G/vl);j=LocateVex(G/v2);/找vl和在G中的位置G.arcsij.adj=w;if(lnclnfo)scanfsjGarcsijinfo);G.arcsji=G.arcsij;returnOK;StatusCreateDG(M

28、Graph&G)/构造有向图intij.kJncInfoAv;VertexTypevl,v2;printff11请输入顶点数和弧数和弧的信息(0表示弧不包含其他信息，1表示弧含其他信息：n);scanf(,%d%d%d,/&G.vexnum/&G.arcnum/&nclnfo);printf(请输入d个顶点：XnG.vexnum);for(i=0;iG.vexnum;i+)scanf(,%s,/&G.vexsi);则for(i=0;iG.vexnum;i+)for(i=0;jv2.就甞金2若星龙权时,w输入权)：y.arcnEm)/.J*fork=0；KG.arcr/um;k士亠yscanf(

29、,%s%s%d,/vl/v2,&w);i=LocateVex(G“l);j二LocateVex(G,v2);寻找vl和v2在G中的位置G.arcsij.adj=w;if(lnclnfo)charssINFO_LENGTH;printf(“输入弧的信息:nM);scanf(,%s,/ss);G.arcsi(j.info=(char*)malloc(INFO_LENGTH*sizeof(lnfoType);/strcpy(G.arcsij.infozss);JreturnOK;StatusCreateDN(MGraph&G)/构造有向网/returnOK;StatusCreateUDG(MGrap

30、h&G)构造无向图intij.kJncInfoAv;VertexTypevlzv2;printf(“请输入顶点数和弧数和弧的信息(0表示弧不包含其他信息，1表示弧含其他信息)：n);scanf(,%d%d%d,/&G.vexnumz&G.arcnum/&nclnfo);printfHi输入d个顶点：XnG.vexnum);fori=0;iG.vexnum;i+)scanf(,%s,/&G.vexs(i);for(i=0;iG.vexnum;i+)/始化矩阵for(j=0;jG.vexnum;j+)G.arcsij.adj=INFINITY;printf(请输入d对顶点关系，格式为vvw(若是无

31、权图，w输入1,若是有权图，则w输入权):XnG.arcnum);fork=0;kG.arcnum;k+)scanf(,%s%s%d,/vl/v2z&w);i=LocateVex(G”l);戶LocateVex(G2);寻找vl和v2在G中的位置G.arcsij.adj=w;if(lnclnfo)charssINFO_LENGTH;printf(H输入弧的信息:n“);return亠亠二/scanf(,%s,/ss);G.arcsij.info=(char*)malloc(INFO_LENGTH*sizeof(lnfoTypW;:厂strcpy(Garcsijinfo,ss);yStatusC

32、reateGraph(MGraph&G)/采用邻接矩阵表示法构造图Gprint1请输入图的类型，输入数字(DG为6DN为1,UDG为2,UDN为3上nH);scanf(“d蔦&Gkind);switch(G.kind)caseDG:CreateDG(G);return0K;构造有向图GcaseDN:CreateDN(G);returnOK;/构造有向网GcaseUDG:CreateUDG(G);returnOK;构造无向图GcaseUDN:ICreateUDN(G);returnOK;/构造无向网Gdefault:returnERROR;intFirstAdjVex(MGraphG,intv)

33、寻找第一个邻接点inti;fori=0;iG.vexnum;i+)if(G.arcs(vi.adj!=INFINITY)x-jeturntfIu良CreturnNOTFOOnD;亠00*intNextAdjVex(MGraphGJntvjntw)寻找除了第一个邻接点的下一个邻接点inti;for(i=w+l;iG.vexnum;i+)if(G.arcs(v(i.adj!=INFINITY)returni;returnNOTFOUND;voidPrintGraph(MGraphG)/打印邻接矩阵inti,j;prints邻接矩阵如下:W);fori=0;iG.vexnum;i+)printfCs

34、G.vexsti);for(j=0;j=0;w=NextAdjVex(G/v/w)if(!visitedw)dfs(G.w);voidDFSTraverse(MGraphG,Status(*visit)(intv)/深度优先遍历，调用深搜/Outputvislt;printf(下面操作深度优先遍历，结果如下：n);intv;for(v=0;vG.vexnum;v+)visitedv=FALSE;for(v=0;vG.vexnum;v+)if(!visitedv)dfs(G,v)；voidBFSTraverse(MGraphG,Status(，visit)(intv)/广度优先遍历图printf

35、下面操作广度优先遍历图，结果如下:W);intvzw;dequedq;for(v=0;vvexnufri;v+)visitedfv/alse;亠亠亠for(v=0;j-jZxffOrrGviif(!visitedv)visitedv=true;visit(v);dq.push_back(v);while(!dq.empty()intu=dq.front();dq.popront();for(w=FirstAdjVex(G/u);w=0;w=NextAdjVex(G/u/w)if(!visited(w)visitedw=true;visit(w);dq.push_back(w);/if/whil

36、e/WforvoidlnsertVex_UDG(MGraph&GVertexTypev)/插入无向图的一个顶点,zy7.15intij=O;strcpy(G.vexsG.vexnumLv);for(i=0;i=G.vexnum;i+)G.arcsG.vexnumi.adj=G.arcsiG.vexnum.adj=INFINITY;G.arcsG.vexnumi.info=G.arcsiG.vexnum.info=NULL;G.vexnum+;voidDeleteVex_UDG(MGraph&GertexTypev)/删除无向图的一个顶点,zy7.15intik=0k=LocateVex(G/v

37、);forj=0;jG.vexnum;j+)if(G.arcsjk.adj)if(G.arcsjk.info)free(G.arcsj(k.info);G.arcnum-;for(j=0;jG.vexnum;j+)if(G.arcsk(j.adj)if(G.arcsk(j.info)free(G.arcsk(j.info);G.arcnum-;for(j=k+l;jG.vexnum;j+)strjG.vexStHkq1严fori=0;iG.vexniSn;i+V|yG.arcsi(j-l=G.arcsij;fori=0;iG.vexnum;i+)for(j=k+l;jG.vexnum;j+)G

38、.arcsj-li=G.arcsji;G.vexnum-;voidlnsertArc_UDG(MGraph&GertexTypevzVertexTypew)/插入无向图的一条弧或边刊7.丄5intvlzwljeap;charinfo(INFO_LENGTH;vl=LocateVex(G/v);wl=LocateVex(Gzw);G.arcnum+;G.arcsvlwl.adj=l;G.arcswlvl.adj=l;printfC*该图的边是否有信息？输入1(是)或0(否：n-)；scanfCd&leap);if(leap)printf(嚇入弧的信息：n“)；scanf(”s”nfo);G.ar

39、csvlwl.info=(char*)malloc(INFO_LENGTH*sizeof(lnfoType);/strcpy(G.arcsvlwl.info,info);voidDeleteArc_UDG(MGraph&GertexTypeVertexTypew)/删除无向图的一条弧或边,zy7.15Intvl,wl;vl=LocateVex(G/v);wl=LocateVex(Gzw);G.arcs(vlwl.adj=INFINITY;23G.arcs(wlvl.adj=INFINITY;if(G.arcsvlwl.info)free(G.arcsvlwl.info);#intminimum

40、(MiniSpanTrejflagFlag山intn)intmin=99999zpl=-l;for(inti=O;in;i+)if(Flag(i.lowcost!=0&FIagi.lowcostmin)min=Flagi.lowcost;pl=i;returnpl;voidMiniSpanTree_PRIM(MGraphGzVertexTypeu)intij；intk=LocateVex(Gzu);for(j=0;jG.vexnum;j+)初始化if(j!=k)strcpy(closedge(jadjvex,u);closedgej.lowcost=G.arcskj.adj;printf(”最

41、小生成树如下:n)；closedgekj.Iowcost=0;for(i=l;iG.vexnum;i+)k=minimum(closedge/G.vexnum);printfH%10s%10sn,/closedgek.adjvex/G.vexsk);closedgek.lowcost=0;for(j=0;jG.vexnum;j+)if(G.arcskj.adjclosedgej.lowcost)strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcsk(j.adj;printfCV)；voidShortestP.c!/Dljkrtra求

42、篇團&药学定应到其亲顶煮的最短路径PM，及其帯权长度Dv若PW拐Tfturd是从vo到V当前求的最短路径的顶点/finalvl为TRUE当且仅当v属于S,即求得了从vO到v的最短路径inti“w;boolfinalMAX_VERTEX_NUM;for(v=0;vG.vexnum;v+)finalv=false;Dv=G.arcsvOv.adj;for(w=0;wG.vexnum;w+)Pvw=false;/设空路径if(DvINFINITY)PvvO=true;Pvv=true;DvO=O;finalvO=true;/|FJ始化，vO顶点属于S集开始主循环，每次求得的vO到某个顶点的最短路径，

43、并加v到S集for(i=l;iG.vexnum;i+)intmin=INFINITY;for(w=0;wG.vexnum;w+)if(!finalw)if(Dwmin)v=w;min=Dw;#finalv)=true;for(w=0;w=O&min+G.arcsvw.adjDw)Dw=min+G.arcsvw.adj;for(intj=O;jG.vexnum;j+)PwU=Pvj;/P(w=Pv;Pww=true;printf(,dijkstra算法求%s到各顶点的最短距离如下:XnG.vexsfvOj);for(i=0;i0&DiINFINITY)printf(s,%s):%dXnG.vex

44、slvOj.vexsfiJli);elseprintf(”(s,%s):NONEnjG/exsvO6vexsi);intmain()printf建立图的邻接矩阵拿拿車車*拿車*拿車車拿車*拿拿*n”)/printf(,INFINITY6dn,JNFINITY);CreateGraph(G);printfPrintGraph(G);DFSTraverse(GQutput);printfCAn)；BFSTraverse(GzOutput);旳f(Tj：二Jprintf(H的起始顶点：nu);VertexTypeu;scanf(,%s,/u);MiniSpanTree_PRIM(Gzu);print

45、f(”请输入最小路径的起点：nH);PathMatrixP;ShortPathTableD;intvO;VertexTypev;scanf(“s“M；vO=LocateVex(G/v);ShortestPath_DIJ(G,vO卫D);/VertexTypevv#ww;printf(接下来的操作时插入一个顶点，请输入顶点：n);scanf(“svv);lnsertVex_UDG(G,w);PrintGraph(G);printf(n深度优先访问为：J；DFSTraverse(G/Output);printf(,n,)；printf(n广度优先访问为：J；BFSTraverse(G/Output

46、);printf(,nH)；printf(-接下来的操作时删除一个顶点，请输入要删除的顶点n”);scanf(”s*v);DeleteVex_UDG(Gzvv);PrintGraph(G);printfC深度优先访问为：冷；DFSTraverse(G/Output);printf(,n,)；printf(M广度优先访问为：J;BFSTraverse(G/Output);printf(,n,)；printf(接下来的操作时插入一条弧或边，请输入边(vv)：nH)；scanf(,%s%s,/vv/ww);InsertArcUDGfGVAvw);PrintGraph(G);DFSTravpsGQue

47、ut腳int$(加”printf(/矗宪気讣赵2亠亠匸BFSTrav秦乂涵应Jhtfn”)；printfC接下来的操作时删除一条边或弧，请输入边(vv)：岸);scanf(,%s%s,/vv/ww);DeleteArc_UDG(G“VMW);PrintGraph(G);DFSTraverse(G/Output);printf(,n,)；printf(H广度优先访问为：J；BFSTraverse(G/Output);printf(,nM)；e/return0;结果：1：测试最短路径：图(2)|xXXKXXXXKMMXXXKXXXXKM/Tpirn|J；MXXXKXXXXKMMXXXMXXXXKX

48、MX慎输入因的类型轲入数字（DG%Q矗丿丄UDG为2,UDN为3）,扫输入顶点数和弧数和弧的信息（嫌示弧不包含其他信息.1丢示弧含其他信息）:680情输入6个顶島vOvlv2u3v4v5学1V专对顶点矣系若uu2,则格式为u2U（若是无权图初输入4,若杲有权图，贝！邻接矩阵如下,21474836472147483647214748364?1002147483647214748364?21474836472147483647214748364?21474836472147483647214748364721474R3647214718364?214748364721474836472147483

49、64721471836T?圧面操作探度忧先遍历.结果如下.u0u2u3u5u4ul丁面擬作广度优先遍历因，结果如下；u0u2u4v5v3vl槁输人最小路径的赶点，vOIU畑5算法求出龍到苦顶点的最短距离如下,:NONI：:NONEUA：5HCu0,u4：30:60Pressanykeytocontinue214748364750214748364220214748361?2147483647214748364?21474836472147483647214748364?214748364721474836471060214748364?vOu5100uOu210uHu430u丄u25u2u350v3v5lbu4u3