数据结构实验报告四

1、甘肃政法学院本科生实验报告()姓名：学院:专业：班级：13级实验课程名称:数据结构实验日期:2014年5月30日指导教师及职称：实验成绩：开课时间：2013-2014学年第二学期甘肃政法学院实验管理中心印制实验题目树形结构小组合作否姓名班级学号一、实验目的8.1实现图的邻接矩阵和邻接表储存8.2实现图的遍历算法8.3求所有深度优先遍历序列8.4用图搜索方法求解迷宫问题8.5求有向图的简单路径8.6求无向图的深度优先生成树和广度优先生成树8.7用普利姆算法求最小生成树8.8釆用克鲁斯卡尔算法求最小生成树8.9釆用狄克斯特拉算法求有向带权图的最短路径&10采用弗洛伊德算法求有向带权图的最短路径.实

2、验环境安装了Windows7操作系统，并且安装了MicrosoftVisualC+6.0。三、实验内容与步骤1、安装MicrosoftVisualC+6.0。2打开MicrosoftVisualC+6.0!1!实验过程:8.1实现图的邻接矩阵和邻接表储存编写一个程序algo8-l,实现不带权图和带权图的邻接矩阵与邻接表的相互转化算法、输出邻接矩阵与邻接表的运算并在此基础上设计一个主程序完成如下功能：（1）建立如图所示的有向G邻接矩阵，并输出之；（2）由有向图G的邻接矩阵产生邻接表，并输出之；（3）再由（2）的邻接表产生相应的邻接矩阵，并输出之reuwiNj：冷创建簫ni：作空円（bj厂廉加列期

3、工作空冈l从（KFroi：二J厂平台旧:方一|门-*Win32新建工程l-ATLCOMAppWIzordraciuatcrRcfioufccTypeWi2ardSnCutomAppWiardProjectSISAPIExtensionWardMokefileDevStudioAddinWizord&Extended8wicdPrueWMadMFCActiveXControlWirdMFCAppWizard(dll|jcc筲Win32Application*nwin32ConooleApplicationWin32Dynomic-LInkUbrary?dVVin32StaticLibrary选择

4、uHello,world!程序”您拔要创蹇什么类型的控制台程序?一个空工程E)一个简单的程序Q个-Hello,Worldf程序(W)一个支MFCfig序M选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp8-l的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#inchide“algo8l.cpp”。运行程序，如下图：SC;TDebugJFF.exe1有向图G的邻接矩阵:05co7coco4053CO88888896053cococo10图G的邻接矩阵转换戚邻接表二0：131：22：053：254：35

5、：04图G的邻接表转换成邻接邻阵,05CO?88cococococococoCOCOcoPressanyKeytocontinue输入代码如下:/婷子.cpp:DefinestheentrypointFortheconsoleapplicationttincludestdafx.h文件名:exp8-1.cppttincludettincludettinclude,Balgo8-1.cppexternexternexternexternuoidMatToList1(MGraptiALGraph*&);voidListTot1at1(ALGraph*,MGraph&);uoidDispMatl(M

6、Graph);uoldDispAdj1(ALGraph*);以下外部函数在goA1-cppvoidnainOinti,j；MGraphg,g1;ALGraph*G;intftMAXU6=0,5,INF,7,INF,INF,8,INF,0,INF,INF,9,INF,IHF,5,0fINF,6,3,INF,INF,INF,1,0；-g.n=6;g.e=10;建立图中有向带标图G的邻接矩阵for(i=0;ig.n;i+)For(j=0；jpWiznrd3Clunt:rClcnourccTypeWixMrdH5CustomAppWi?ard(ftDotoba&cProjedDcv3ludioAdd-

7、inWUord話ExtendedSlorodProcWizardAISAMExtensionWlrdrMakefile裾MFCActiveXConlrolWiard由MFCAppWi2ard(dll)KJMFCAppWi2ard(excjJsNrwDatsbaeWixardTlUtilityPfoicd为Win32Applicationnwin32ConooloApplication1Win32Dynomlc-LInkLlbvoryWin32SStlcLibrevyrew(N)：2tBCii9daiidaii7仪壑C：zhangdandan7e刨尬插的工作空冋Bl广加伽御沛工件041阀L从KT

8、(O)：I_d平台旧：*Win32选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?srsin一个空工6(E)一个简单的程序(S)Q个Hello,World严程序(W)个支持MFC的程序(M)选择Fileview复制algo8-l和algo8-2和Graph到工程文件中。把主文件大开，用exp8-2的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#includet6algo8-l.cpp和#inchidealgo82cpp”。运行程序，如下图:3-C:1222DebugL222.exe0:1C5)3C7)1:22：053

9、：2C5)5C6)4：35：0C34(1从顶点0开始的DFSC递归算法:012543从顶点0开始的dfsE递归算法从务上謠始鮎b；sIe递归算法013254Pressanykeytocontinue输入代码如下:ttincludeBlstdafx.h11ttincludettincludettincludealgoS-l.cppttincludeialgo8-2.cpptBexternuoidexternuoidexternuoidexternuoidexternuoidexternuoidMatToListl(MGraph9ALGraphDispfidj1(fiLGraph*G);DFS(A

10、LGraph*G,intu);DFSKALGraph*G,intv);DFS2(ALGraph*G,intu);BFS(ALGraph*G,intu);*&)；以下外部函数在alQ08-1.cpp中以下外部函数在al98-2卬卩中uoidnain()inti,j；MGraphg;fiLGraph*G;intAMAXU6=0,5,INF,7,INF,INF,(INF,0,4,INF,INF,INF,8,INF,0,INF,INF,9,INF,INF,5,0,INF,6,IHF,IHF,IHF,5,0,IHF,3,INF,INF,INF,1,0;_g-n=6;g-e=10;建立图8.1中有向带标图

11、G的邻接矩阵for(i=B;ig.n;i+)For(j=0;jg.n;j+)g.edgesij=fiij;G=(fiLGraph*)nalloc(5izeof(ALGraph);MatToListl(g,G)；图G的邻接矩阵转换成邻接表耐ntW图G的邻接表:册)；DispAdj1(G)；prints从顶点研始的DFS(递归算法):中)；DFS(G)；printF(rT);PMintfC-顶点研始的DFS(非递归算法):n)；DFS1(G,fi);printf(-K顶点研始的BFS(非递归算法):W);BFS(G,0);pKintF(,inM);8.3求所有深度优先遍历序列编写一个程序algo8

12、-3,釆用邻接表存储图。新建工程文侔re|:r件区览它文档|占ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrdiTICugtomAppWi?ard)选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?一个空工程(E)一个简单的程序Q个Hello,Worlds程序(W)一个支持MFC的程序(M选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp8-3的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#inchide“algo8l.cpp”。运行程序，如下图

13、：3C:4Debug4.exe-图G的邻接表：0：134从啸点1岀发的所有深度优先序列:10324103421042310432i23041234012403i24301304213240Pressanykeytocontinue输入程序如下:/置已访间标记/如果已访问所有顶点，则输岀访问序列/P指向顶点U的第一条弧的弧头结点uisitedu=0;voidDFS(ALGraph*G,intu)ArcNode*p;visitedv=1;printFCdp=G-adjlistu.firstarc;while(p皆NULL)if(uisitedp-adjuex=8)DFS(G,p-adjuex);p

14、=p-nextarc;置已访问祢记側鼬蠶喘节点/gp-adjuex顶点未访间，递归访间它卩指向顶点u的下一个边节点ttincludestdafx.h文件名:exp8-3.cppttincludettincludettincludealgo8-1-cppexternuoidMatToList(MGraph,ALGraph*&);以下外部函数在algo8-1.cpp中externuoidDispAdj(ALGraph*);/intuisitedHAXV;voidDFSALL(fiLGraph*G,intu,intpath,intd)ArcNode*p;uisitedv=1;pathd=u;di;i

15、F(d=G-n)for(intk=0;kp=G-adjlistu.firstarc;while(p?=NULL)iF(uisltedp-adjuex=0)若p-adjuex顶点未访|可,递归访问它DFSALL(G9p-adjvex,path,d);p=p-nextarc;P指向顶点u的下一条观的弧头结点uisitedu=0;voidmain()intpathMAKU,i,j,u=1;MGraphg;ALGraph*G;g.n=5;g.e=8;intfiMAXUMAXU=8,1,8.1,1,1,8,8,1,0,1,1,1,1,1.0,1,1,0,1,1,0;for(i=0;ig.n;i*)建立教

16、程中图8.1的邻接矩阵For(j=0;jg.n;j+)g.edgesij=Aij;MatToList(g,G);for(i=0;i);8.4用图搜索方法求解迷宫问题设计一个程序，实现如下功能:（1）建立教程所示港宫对应的邻接表表示。（2）采用深度优先遍历输出所有迷宫的路径。新建工程Fll3|文命re|工帚区览它文档|4ATLCOMA4pWiznrdjCluntcrClcnourccTypeWixMrdTlCugtomAppWi?ardUtPDotobe&cProject$*Dcv3ludioAdd-inWlzoid强ExtendedSlorodProcWizardAISAMExtensionW

17、izardMakefile宙MFCActiveXConlrolWiard0MFCAppWi2ard(dllj0MFCAppWi2ard(excjNrwDatsbaceWizardT(UtilityProied宣Win32ApplicationnWin32ConooloApplicationWln?2Dynomlc4_lnkUbroryJWin32StaUcLibrevyrewiw)：.hongdondottWlO：C：zhangdandan7平台旧:Win32选择Hello,world!程序”您拔要创蹇什么类型的控制台程序?一个空工程E)一个简单的程序Q个Hello,Worldf程序(W)一个

18、支MFCfig序M选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp84的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-l中主函数备注掉，并且手动引入#include4424Ji尸4444zkccc4434zkccc3C:：199DEbug199g333ccc3213333111222211各:-continues1234kany:*显各kp血p-mmnfa..3.4店的宀吕宀吕宀吕宀吕4555555-1.采一卷米.一输入程序如下:111ttincludestdafx.h文件名:exp8-4.cppttinclude

19、includettdefineMaxsize180ItdefineM4ttdefineN4以下定义邻接表类型typedefstructfiNodeinti,j；structAHode*nextarc;邻接表头结点的类型指向第一条边ArcNode;typedefstructUnodefircNode*Firstarc;VHode;typedefstructUHodeadjlistM*2N+2;ALGraph;111111typedefstruct111111intintBox;structBoxintdataMaxSize;length;PathType;intuisitedM*2N+2=0;i

20、ntcount=0;uoidCreateList(fiLGraph*&G,int建立迷宫数组对应的邻接表G從磁曇类型ngN2Jinti,j,i1,j1,di;ArcHode*p;G=(ALGraph*)malloc(sizeoF(ALGraph);For(i=0；iM*2；i-)给邻接表中所有头节点的指针域置初值for(j=0;jH+2;j+)for(j=0;jadjlistij.Firstarc=HULL;for(i=1;i=M;i*+)/检查呵中毎个元素For(j=1；j=N;j+)if(mgij=0)di=0;while(di4)switch(di)case0:i1=i-1;j!=j;b

21、reak;case1:i1=i;j1=j+1;break;case2:i1=i+1;ji=j;break;case3:i1=i,j1=j-1;break;if(ngi1j1=0)为可走方块i=i1;p-j=j1；p-nextarc=G-adjlistij.Firstarc;/将叩节点链到链表后G-adjlistij.firstarc=p;di+;uoidDispAdjCALGraph*G)/输岀邻接表Cintij；ArcNode*p;for(i=0;iM+2;i+)for(j=0;jadjlistij.Firstarc;luhile(p?=NULL)printf(-(%(!,%d)1B,p-i

22、,p-j);p=p-nextarc;printF(-nBi);uoidFindPath(fiLGraph*G,intxi,intyi,intxe,intye,PathTypepatArcNode*p;uisitedxiyi=1；置已访间标记path.datapath.length.i=xi;path.datapath.lengthj=yi;path.length*;iF(xi=xe&yi=ye)printF(,B迷宫路径d:Bi,*+count);For(initk=8;kB);p=G-adjlig：txiyi.Fir5tarc;p指向顶点u的第一条边顶点while(p?=NULL)ip-j=

23、0)/若(p-i,p-j)方块未访问，递归访问它FindPath(G,p-i,p-j,xe9ye,pth);p=p-nextarc;/pfe向顶点u的下一条边顶点迷宫数组输出邻接表ui5itedxiyi=8;ALGrapti*G;intngM*2H*2=1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,1,1,1,1,1,1,1,1；CreateList(G,mg);printFC-迷宫对危的邻接表:n,B);Dispfidj(G);PathTypmpath;intF(”济有苗迷宫路径:W)；FindPath(G,1,1,M,N,path);8.5求有向图

24、的简单路径编写一个程序exp8-5,实现如下功能：（1）输出所示的有线图G从顶点5到顶点2的所有路径:（2）输出所示的有线图G从顶点5到顶点2的所有长度为3的轻:输出所示的有线图G从顶点5到顶点2的最短路径:新建工程WI3frewiNi：zliuii9liBdan7,C：zhangdandan7e刚尬插的工作空冋Bl於力1细前：r你空厂从T(Q)：Iz平台旧：*Win32选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?Bf?E3一个空工6(E)r一个简单的程序(习个Hello,World严程序(W)个支持MFC的程序(M)选择Fileview复制algo8-l和Graph到工

25、程文件中。把主文件大开，用exp8-5的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#includealgo8-1.cpp运行程序，如下图：BC:3546Debug3546.eKe图G的邻接急0:131：2TOC o 1-5 h z2:053:254：35：0134|从顶点5到2的所有路径：581250325125325432i从顶点弓到2的所有长度为3路径二581250325432从顶点5到2的最短路径；512Pressanykeytocontinue输入代码如下:ttincludestdaFx.h打文件名：Exp-5.cpptti

26、ncludettincludettincludeB,algo8-1-cppexternvoidMatToList(MGraph,ALGraph*&);externuoidDigpfidj(ftLGraph*);/intuisitedMAXU;/全局数组voidPathAlU(ALGraph*G,intuintu,intpath,inti输岀图呻从顶点u到u的所有简单路径ftrcNode*p;intj,n;ui5itedu=1;卩=G-adjlistu.Firstarc;P指向顶点皿的第一条边while(p?=HULL)adjvex；为m的邻接顶点if(n=u)pathi+1=u;For(j=0

27、;jnextarc;找的下一个邻接顶点uisitedu=O;uoidPathA112(ALGraph*G,u,int1,intpath,intd)Kvrt*叵焙nJ瑶更、DIP膘咂护-聖盖OIP蹑峡昌伪汕、-V-oHrHanelrrEMlnbIrlFoumzefjnb=H【己d-Hs-HnIKdxS05i二lWIWLlegLIH4UOJU-4.5二fiXUldnh宀IrlludJBd4S二2n2r-14u-rMgA4占4Jon4ssisQH=n峡修烁、(【jmEdpuun兰-rn41HJ*udm寿-lsmedzMOUS3匚-H旺撅1删丘娠亘図埋s塩叵堆毎蛊、丄=pm砸国wASS

28、Ksn径、*占和2LKdud二Elned二llJ)zlETUlnedZ叵灼E3S*叵溶居归峡昌悭和、缶丄邑S3芸峽亘鰹累岳n苓/7xe二DEAdNul21nN=id)QI-HU冷一j希4JS-H4=4STHPE人肆d宀zcrjzRUMd二ulns.pgzLtuTd半二亍二茜“匕莒4(IHHP比小n=Hn-IIMn丄巳edr+p-LH【=:4JH5nIKd*apohpuu二占pul队非空则执行qurear.parent=-1;uhile(rontrear)k=qu4=ront.uno;出队lev=quFront.leuel;if(k=v)i=0;j=front;while(j?=-1)Mtiim

29、leu;找到顶点u,返回p=G-adjlistfk.Firstarc;while(p!=NULL)adjuex=O)若未访问过adjuex;访问过的邻接点入队qurearleuel=leu+1;qurea-parent=Front;p=p-nextarc；找顶点i的下一邻接点return-1;如果未找到顶点j,返回一特殊值7uoidmain()inti,j;intu=5,u=2,d=3;intpathMAXU;MGraphg;AiLGraph*G;intAMAXU6=,g.n=6;g.e=10;For(i=0;ig.n;i*+)建立图910的邻接矩阵For(j=D;jg.n;j*+)g.edg

30、esij=Aij;G=(ALGraph*)malloc(sizeof(ALGraph);l1atToList(g,G);图G的邻接矩陈转换成邻接表printFC1图G的邻接表W)；OispAdj(G);For(i=O;ig.n;i+)uisitedi=0;printfCJA顶点却到加的所有路径：n-,u,v);path8=u;uisitedu=1;PathAll1(G,ufu,path,8);p厂intF(从预点却到U的崩有长度为d路径:XnBu,u,d);PathA112G,u,u,d,path,-|);printF(,ni,);For(i=O;ig.n;i*+)uisitedi=0;p厂i

31、ntFL从顶点知到灯的最短路径：n-,u,u);For(i=O;ig.n;i+)uisitedi=0;j=ShortPath(G,u,v,path);For(i=8;i=j;i+)printfCSd-jpathfi);printfCAn);&6求无向图的深度优先生成树和广度优先生成树编写一个程序algo8-2,输出所示的有线图G从顶点3出发深度优先生成树和广度优先生成树。新建工程文命r|rtt=e览它文4$|4ATLCOMAppWi2ardTHCiuntcrClcnourccTypeWixnrd53CuslomAppWi?ard宙DatableProjed$Dcv3ludiuAdd-inWlz

32、atd总ExtendedSlorodProcWizardAISAMExtensionWizardr：-Makefile&MFCActiveXConlrolWiard由MFCAppWi2ard(dll)0MFCAppWi2ard(excjjXNrwDstsbaeWizardT(UtilityPfoied为Win32Applicationnwin32ConooloApplicationIWin32Dynomlc-.lnkLlbroryJWin32SStlcLibrevyrew(Nj：zliungdaiBdaii7C：zhangdandan7a刚尬攝的工作空冋(Bl广序如何汕I：件0冋阀L从T(Q)

33、：I丄平台旧：*Win32选择Hello,world!程序”您啤要创蹇什么类型的控制台程序?一个空工程(E)一个简单的程序Q个Hello,World?-程序(W)一个支持MFC的段序(M)选择Fileview复制algo8-l和Gmph到工程文件中。把主文件大开，用exp8-6的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#includealgo8-1.cpp,9程运行序，如下图：输入程序如下:ttincludestdafx.h文件名:exp8-6.cppttincludettincludeitincludealgo8-1-cpp1e

34、xternuoidMJtToList(MGraph,fiLGraph关&);externuoidDispAdj(ALGraph*);/intuisitedfHAXUJ;uoidDFS(ALGraph*G,intu)全局数组ArcNode*p;visitedv=1;p=G-adjlistv.firstarc;while(p!=NULL)緒訥臨-条边iF(uisitedp-a时若p-2djuox顶点未访问，递归访间它printf-,u,p-adjuex);输出生成树的一条边DFS(G,p-adjuex);P指向顶点u的下一条边ArcNode*p;intimtFor定义循环队列并初始化voidBFS

35、(ALGraph*G,intu)queueMA2Uront=0,rear=fl;w,i；(i=8;in;i+)uisitedi=O;visitedv=1;rear=(rear+1)MAXU;queuerear=u;while(Front?=rear)front=(front*1)WAXU；Front=(front*1)%HAXU;w=queuefront;岀队并赋结押p=G-adjlistw.firstarc;找与顶点两馳第一个顶点while(p?=NULL)iF(uisitedp-adjuex=0)若当前邻接顶点未被访问printF(-ad,d-Mpadjuex);/输岀生成枕|的一条边ui

36、sitedp-adjuex=1;置该顶点己被询可的标志rear=(rear+1)MAXU;该顶点进队queuerear=p-adjuex;p=p-nextarc；我下一个邻接顶点printf(iBnBi);uoidnain()inti,j；MCraphg;ALGraph*C;intfiMAXU11=0,1,1,1,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1.0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,fl,fl,fl,0,1

37、,1,1,fl,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0；g.n=11;g.e=13;建立图8.13的邻接矩阵for(i=0;ig.n;i+)For(j=O;j);DispAdj(G);iiprin申图G的邻接表:W);DispAdj(G);printffXn-1)；For(i=0;ig.n;i+)visitedi=0;prints探度优先生成树叩)：ftFS(G,3);printfCn11);For(i=8;ig.n;i+)uisitedi=0;printfC

38、-J度优先生成树：J；BFS(G,3);printf(n);8.7用普利姆算法求最小生成树编写一个程序设计一个算法对所示无限带权图G,采用普利姆算法输出从顶点0出发的最小生成树新建工程nnm文命r|:r帚区览它文档JATLCOMAppWizardjCluntcrClcnourccTypeWixnrdiFICugtomAppWi?ardDotoba&cProjediDcv3tudiuAdd-inWUcvil能ExtendedSlorodProcWizardISAMExtensionWizardrpMakefile待MFCActiveXConlrolWiard宙MFCAppWi2ard(dll|S

39、JMFCAppWi2ard(excjNrwDtsbaccWizardTlUtilityPfojedXWin32Application二Win32ConooloApplicationWin32Dynomic-LInkLibraryWin32SttlcLibraryrewiN)：2liaii9daiidaii7ewici：C：zhangdandan7平台旧：*Win32选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?一个空re(E)一个简单的程序(S)/V算舟,4J.2,3_-By05014o/3里边边边边边普Pressanykeytocontinue输入程序如下:ttinclu

40、destdaFu-h/文件名:exp8-7.cppitincludettincludeBialgo8-1.cppexternvoidDispMati(MGraph);外部函数在algo8-1-cpp中voidPrim(MGraptig,intu)intlowcostMAXU,nin,n=g.n;intclosestfMftXU,i,j,K；For(i=O;in;i+)给lowcostQclosest置初值lowcosti=g.edgesui;closesti=u;for(i=1;in;i*+)找岀nT个顶点min=INF;for(j=0；jn;j-)在(U-U)中找出离U最近的顶点kiF(lo

41、wcostj!=6&lowcostjmin)min=lowcostj;k=j;printF(IB边(盅d丽)祓%:%dnIB,closestk9kvmln);lowcostk=0;标记k己经加人UFor(j=0;jn;j+)修改数组lowcoctQclosestif(g.edgesfkj?=0&g.edgeskjlowcostj)lowcostj=g.edgeskj;clospstj=k;uoidnain()inti,j,u=3;MGraphg;intfiMfiXUMflXU=0,5,8,7,INF,3,5,0,1*,INF,INF,INF,INF,INF,INF,5,9,1,3,INF,9,

42、IHF,1,0;g.n=6;g.e=10;for(i=O;ig.n;i+)建立图&亿的邻接矩阵for(j=0;jg-n;j*+)g.edgPSij=Aij;图G的邻接矩阵:W)；DispHat1(g);普里姆算法求解结果An-);Prin(g,O);HI8.8采用克鲁斯卡尔算法求最小生成树编写一个程序所示无限带权G,采用克鲁斯卡尔算法输出从顶点0出发的最小生成树新建工程文侔re|:r件区览它文档|占ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrdiTICugtomAppWi?ard)选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?一个空工

43、程(E)一个简单的程序Q个Hello,Worlds程序(W)一个支持MFC的程序(M选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp8-8的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#inchide“algo8l.cpp运行程序，如下图：JBC;0Debug0.exeB图G的邻接矩阵0587cooocx3CO9CO3oo?coi0克鲁斯卡尔算法求解结果0.5）：3CU2：43M5Pfcssanykeytocontinue输入程序如下:酮鬆第V袈层、二UHnasn?*IJU-HHio*-二馆uzh

44、asn兰-rtusTUSra3Erapural?T4U-H?兰-Hu兰-hulli告D3二eJISFHDMon.H丄ybl+f-w/v二a宀掘险曹二sM-K豊責二zu丄T-二tzr3二！JLLJ*dule:l當：3M归桓匕3|轻任?1:丄凶也悴皑-W叵Bw、二丄丄二匸中du亠二r=us26p26g二汽3二Hnia二Hnildu2bllx=lnsabpa5r*c-WVQHULo*(：w6yfQNifdulalA=W:U-Hllde3526pL!JtusP-Hon二A3Q.5-HQDIO*uxa皆p:34U-H:U-H4un4s4epaJdf4鬆玛廉喘、6=UJXUHau-l-1l4-aMtdd:

45、rL80edDnEuntITO-HP4Sepnr-Hou-HltddT8l8dxd卯世収、S3M0CSfor(i=0;in;i+)useti=i;RT；k表示2j=0;中边while(kn)曜遡骅寸的第几条边初值为生成的边鸟柬职器齧Fm1=Ej.u;n2=Ej.u;sn1=usetml;sn2=vsetm2;if(sn1?=sn2)两顶点属寸printF(B,(Zd必d):盅drr.m,n2,Ej.w);.I八、I5|ZII丿一1k*+;for(i=0;in;i+)iF(useti=sn2)useti=sn1;sn1J*；扫描下一条边voidnain()inti,j,u=3;MGraphg;E

46、dgeEMfiXE;intAMAXUMAXU=FS,O,J|5INF,INF,INF,8,4,0,5,INF,9,INF,INF,INF,5,0,1,；g.n=6;g.e=10;for(i=8;ig.n;i*+)建立图816的邻接矩阵For(j=8;jg.n;j+*)g.edgesij=Aij;SortEdge(g,E);printfC*图G的邻接矩阵:ArT)；DispMatl(g);printfC*#斯卡尔算法求解结果：n);Kruskal(E,g.n,g.e);printfCn11);8.9采用狄克斯特拉算法求有向带权图的最短路径编写一个程对所示无限带权图G,采用克鲁斯卡尔算法输出从顶点

47、0的最短路径的长度和最短路径。新建工程学st文侔re|:r件区览它文档|4ATLCOMAppWizardTHCluntcrClcnourccTypeWixNrd53CustomAppWi?ard)厂平feiei：*Win32选择Hello,world!程序”您馥要创蹇什么类型的控制台程序?一个空工程(E)一个简单的程序Q个Hello,Worlds程序(W)r一个支持MFC的程序M选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp8-9的内容覆盖到主文件由于main()函数被重复定义所以需要备注，把algo8-1中主函数备注掉，并且手动引入#includeal

48、go8-1.cpp,9运行程序，如下图：EC:654Debug654.exe-OD8ODCO2551133300000isenHHncxnknSn5n53S43597113.:5ff匱度度度1snscxnknnJnjnsnJn3L短_EH_8径曰簪Bs簪販8nJ.B.B.B.B.B豆丄2345、QKh:到MiS到到0Ewt000003岀置笛%.7:|1?|期Pressanykeytocontinue输入程序如下:ttincludestdaFx.h文件名:exp8-9.cppttincludettincludeB,algo8-1.cppdefineMfiXU180最丈顶点仝数externuoid

49、DispMatl(MGraphg);夕卜部曲数在.cpp中voidppath(intpath,inti,intu)intk;k=pathi;if(k=u)return;ppath(path,k,u);printfCd,3k);uoidDisPath(intdist,intpath,ints,intn,intu)inti；printfCBpath:);输岀path值For(i=0;in;i+)printf(Bi%3dlpathi);printf(iBXn,B);For(i=0;in;i+)if(si=1)iF(ir=u)Printf(-从d到初的最短路径长度为瑰dt路径为：,u,i7disti)

50、;printf(d,u);ppatti(path丄uj;printfC.dn,i);elseprintFC-从盅d到盅d不存在路径nBB,u,i);uoidDijkstra(MCraphg,intv)intdistMAXU,patht1fiXU;intsMftXU;intmindis,i3j,u,n=g.n;斶蟹化一II0For(i=0;in;i+*)disti=g.edgesui;si=6；u=-1;for(j=0;jn;j*)选取不在s中且具有最小距离的顶点uiF(5j=0&distjmindis)u=j;mindis=distj;5U=1；for(j=0；jn;j*)修改不在s申的顶点的

51、距离IF(sj=0)if(g.edgesujINF&distu+g.edgesujuoidnain()inti,j,u=0;MGraphg;intRMAKU6=5,INF,7,INF,INF,INF,INF,5,0,INF,6,；g.n=6;g.e=10;For(i=0;ig.n;i*+)建立图&的邻接矩阵g.edgesij=Aij;Printf(-pWi2nrd37)Clut)：Id平台旧：*Win32选择Hello,world!程序”您啤要创蹇什么类型的控制台程序?一个空工程(E)一个简单的程序Q个Hello,World厂程序(W)1一个支持MFC的程序(M|选择Fileview复制algo8-l和Graph到工程文件中。把主文件大开，用exp8-10的内容覆盖到主文件。由于main()函