图的遍历和生成树求解实现的课程结构设计

1、图的遍历和生成树求解实现的课程结构设计问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。基本功能1）先任意创建一个图；2）图的DFS,BFS的递归和非递归算法的实现3）最小生成树（两

2、个算法）的实现，求连通分量的实现4）要求用邻接矩阵、邻接表等多种结构存储实现输入输出输入数据类型为整型和字符型，输出为整型和字符二、概要设计1.设计思路：a图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用表示。图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问V的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“

3、先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。图的深度优先遍历：假设从图中某顶点V出发，依依次访问V的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。2.数据结构设计：ADTQueue数据对象：D=a|aGElemSet,i=l

4、,2,3,n,n0ii数据关系：R1=|a,a$D,i=l,2,3,ni-1ii-1i基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。QueueEmpty(Q)初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。EnQueue(&Q,e)初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。ADTQueueADTGraph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR二v,w|v,wGV且P(v,w),v,w表示从v到w的弧

5、，谓词P(v,w)定义了弧v,w的意义或信息基本操作P：CreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。BFSTraverse(G,visit();初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。DFSTraverse(G,visit();初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作

6、失败。DFStra_fen(G)初始条件：图G存在，存在图的深度优先遍历算法。操作结果：从多个顶点对图进行深度优先遍历，得到连通分量ADTGraph;3.软件结构设计：maincreatMGraph_L(G)catadj(gra,G)a,G)e(gra)efen(gra6MiniSpanTfiMiniSpanTRee_PRIM(g|EE_KRUSCALG.vexnum)(G,gra)函数名返回值类型creatMGraphL(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(g

7、ra)intDFSTraversefen(gra)intMiniSpanTreePRIM(g,G.vexnum)intMiniSpanTREEKRUSCAL(G,gra)voidljjzprinadjprint(g*BFSTraverSDFStra(gr*DFSTraverG)三、详细设计定义程序中所有用到的数据及其数据结构，及其基本操作的实现；邻接矩阵定义:typedefstructArcCellVRTypeadj；/VRType是顶点关系类型。对无权图，用1或0表示相邻否;对带权图，则为权值类型InfoType*info；/该弧相关信息的指针ArcCell,AdjMatrixmaxmax；

8、typedefstructVertexTypevexsmax；/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum,arcnum；/图的当前顶点数和弧数MGraph_L；邻接表的定义:typedefstruetArcNode/弧结点intadjvex；/该弧指向的顶点的位置structArcNode*nextare；/指向下一条弧的指针InfoType*info；/该弧相关信息的指针ArcNode；typedefstructVNode/邻接链表顶点头接点VertexTypedata；/顶点信息ArcNode*firstare；/指向第一条依附该顶点的弧的指针VNode,AdjLi

9、st；typedefstruct/图的定义AdjListverticesmax；intvexnum,arcnum；/图的当前顶点数和弧数ALGraph；队列定义:typedefstructQNodeQElemTypedata；structQNode*next；QNode,*QueuePtr；typedefstructQueuePtrfront；/队头指针QueuePtrrear；/队尾指针LinkQueue；2主函数和其他函数的伪码算法；主函数：intmain()ints；chary=y；cout|QQQQQQQQQQQQQQQQQ菜单QQQQQQQQQQQQQQQQQQ|endl；cout|

10、【0、创建一个无向图|endl;cout|【1、显示该图的邻接矩阵|endl;cout|【2、显示该图的邻接表|endl;cout|【3、广度优先遍历|endl;cout|【4、深度优先遍历|endl;cout|5、最小生成树MiniSpanTree_PRIM算法|endl;cout|6、最小生成树MiniSpanTree_KRUSCAL算法|endl；cout|7、连通分量|s；if(s=0)+o；if(o=2)n=0；l=0；o=0；switch(s)case0：cout创建一个无向图：endl；MGraph_LG；creatMGraph_L(G);ALGraphgra;creatadj(

11、gra,G);break;casel：cout邻接矩阵显示如下：endl；ljjzprint(G);break；case2：cout邻接表显示如下：endl；adjprint(gra,G)；break；case3：cout”广度优先遍历：；BFSTraverse(gra)；coutendl；break；case4：cout深度优先遍历：；DFStra(gra)；coutendl；break；case5：if(n=0)cout无权图没有最小生成树；break；elseif(l0)cout若该图为非强连通图(含有多个连通分量)时最小生成树不存在endl；break；elseinti,gmaxmax

12、；for(i=0；i!=G.vexnum；+i)for(intj=0；j!=G.vexnum；+j)gi+1j+1=G.arcsij.adj；cout普利姆算法：endl；MiniSpanTree_PRIM(g,G.vexnum)；break；case6：if(n=0)cout无权图没有最小生成树；break；elseif(l0)couty；if(y=n)break；return0；邻接矩阵存储：intcreatMGraph_L(MGraph_L&G)/创建图用邻接矩阵表示charv1,v2；inti,j,w；cout请输入顶点和弧的个数endl；cinG.vexnumG.arcnum；cou

13、t输入各个顶点endl；for(i=0；iG.vexnum；+i)cinG.vexsi；for(i=0；iG.vexnum；+i)for(j=0；jG.vexnum；+j)G.arcsij.adj=int_max；G.=NULL；for(intk=0;kvlv2w；/输入一条边依附的两点及权值i=localvex(G,vl)；/确定顶点VI和V2在图中的位置j=localvex(G,v2)；G.arcsij.adj=w；G.arcsji.adj=w；for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj!

14、=1&G.arcsij.adjint_max)n+=1；if(n=1)cout这是一个有权图endl；elsecout这是一个无权图endl；cout图G邻接矩阵创建成功！endl；returnG.vexnum；邻接矩阵的输出：voidljjzprint(MGraph_LG)/邻接矩阵的输出inti,j；if(n=0)for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj=int_max)cout0；elsecoutG.arcsij.adj；coutendl；elsefor(i=0;i!=G.vexnum;+i)for(j=0

15、;j!=G.vexnum;+j)if(G.arcsij.adj二二int_max)cout8；elsecoutG.arcsij.adj;coutadjvex=j;arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout图G邻接表创建成功！endl；return1;邻接表输出：voidadjprint(ALGraphgra,MGraph_LG)/邻接表输出inti；for(i=0；i!=gra.vexnum；+i)ArcNode*p；cout

16、i,G.vexsi；p=gra.verticesi.firstarc；while(p!=NULL)coutadjvexnextarc；coutEnd；coutnext=NULL；return1；入队：StatusEnQueue(LinkQueue&Q,QElemTypee)/入队，插入元素e为Q的新的队尾元素QueuePtrp；p=(QueuePtr)malloc(sizeof(QNode)；if(!p)return0；/存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;出队：StatusDeQueue(LinkQueue&Q,

17、QElemType&e)/出队，若队列不空，则删除Q的队头元素，用e返回，并返回真，否则假QueuePtrp;if(Q.front=Q.rear)return0;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return1;判断队为空：StatusQueueEmpty(LinkQueueQ)/判断队为空if(Q.front=Q.rear)return1;return0;广度优先遍历：voidBFSTraverse(ALGraphgra)inti,e;LinkQueueq;for(i=

18、0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi)visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);深度优先遍历：intDFS(ALGraphgra,inti)visitedi=1;intwe1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(vi

19、sitedwe=0)DFS(gra,we);we=we1;return1;intDFStra(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return0;连通分量：intDFSTraverse_fen(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);cout=0;we=nex

20、tadjvex(gr-a,gra.verticese,we)If(!visitedwe.)YESVisitedwe=1;Enqueue(q.we)结束NO开始YESIf(lowcostjmin)&(lowcostj!=0)fIf(gkj0为有权图，此时输出的时候用a代替10000；n=0为无权图，此时输出的时候用0代替10000.b程序中有的功能对某些图是不适用的，比如无权图没有最小生成树，非强连通图没有最小生成树等。所以在程序中又新增了全局变量l,l0时表示为非强连通图，则在求最小生成树时报错。C当程序先创建一个有权图后，n的值会大于1,第二次创无权图时也会被程序认为有权图，所以在程序中在定

21、义全局变量o（初值为0），来判断创建了几次图，当第二次创建图，即o=2时，所有全局变量在开始全归零。程序中可以改进的地方说明；当建立一个图时先得求其连通分量，从而确定全局变量l的值，从而才能判断该图是否有最小生成树。五、测试结果创建一个无权图：JE:C6MyProjectsk课设叭tewt,exeinnmnnmnnmnunnnngmnnmnnoannonnai!【0、仓建一|无问图i【丄、显不该固冃勺邻按矩库!匕显丞该图的邻揍表!0亠度优先遍历iS塗捷忧客遍厉土innmnnm口口mn口口aancononn口口口口口口oaSoonnoi在或最小生咸梃前请去求逐通分量F!6.iniSpanTree

22、_PRI:【7、最小生iniSpanTpee_KRUSCftL请选择菜单、创建一个无向图:i青输入顶点和弧的个数76輸入各个顶点abcdefg-输人一条边恆附的顶点和权ah1输入一条边依附的顶点利权kc1输入一条边依附的顶点和权bd1箭入一条边依附的顶点和权淀1輸入一条边恆附的顶点利权de1输入一条边依附的顶点和权输1建是一个无机图fficW矩阵创建成功！图G邻聲衰创建成功!足否继续？V/n：是否继续?y/n：y请选择菜单；邻接矩阵显示如下:3110009L001100L0000003160100316100030000013000010是否继续？y/n：是否继续？yn：y責选择菜单；怎通分量

23、Mcbedfsr是否继续？y/n：ij请选择菜単：无权图滾有最小空成树是否無瘵？yn=y请选择菜单；7役宙最小生成郴创建一个费强连通的有权图:CfiIyProjects$入各个顶点hedefg金入一条边依附的顶点和权鼬K条边依附的顶点和权c3鼬条边依附的顶点和权d1俞坯条边依附的顶点和权钛条边依附的顶点和权e4叙V条边依附的顶点和权g2丈杲一个有权圈昶邻拱矩阵仓!I建成功|昶邻谨袤创建成功|否继续农少2该圈为非强连適圈（含有多个连通分量时,最小主成树不存在亥圏为非强连通圏含有多个连逋分量,最小-主成捌不存在创建一个有权连通图：g*E:XVCfiMyPxojects创建一个无向商；1请输入顶点和

24、弧的个数S5输入各个顶点；ibcde输入一条边依附的顶点和权ab2输入一条边依附的顶点和权ac3输入一条边依附的顶点和权bd1输入一条边依附的顶点和权脣只一条边依附的顶点和权de4边杲个有权圈图G邻按矩阵刨建咸功I圈G邻接表创建成功|是否继续？y/n=P喜选择菜单：磴通分量=acb&db否继续？y/n=i,賣选择菜单：詈利姆算法匕(0A233曜否继续？必曲事选择菜单；住鲁斯卡尔算法二233是否继绫1y/n=六、用户手册-*E:VC5IyProjects课设4Debugtest.exeH口口口口O.C11!.V:漠卑.【TOC o 1-5 h z!t【氛仓0建广无总:旻f!-舐显丞该1WS矩阵n

25、住、显示该图的邻接表H-3.广鹿備先遍历一亠亠一一亠亠一亠一-氐gB先遍历h鹦、雀通分量5!Lt；iniSpanTree_PEI法?.最小生inISpanTree_KEUSGA法Ii|g口口口g口口口口口口口口口口口口口g口口口口口口口口口口口口口口口E弁求最小生戒树前请先求弃诵分量！慵选择荚卑：a.先选0创建一个图。b.选择y继续操作。c.按照菜单编码选择操作。七、体会与自我评价在做这个程序的时候你首先必须知道图的一些概念，图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并

26、且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。当我们拿到一个图时，我们对该图的遍历就要有一些方法，所以有了深度优先遍历和广度优先遍历，我们要明白这两种遍历是怎么实现的，然后根据我们人脑中的方法把它写成电脑算法。对一个图我们还定义了连通分量，所以将图存到电脑中时，我们对连通分量得有个算法。求图的最小生成树有两种算法，普利姆是从结点出发寻找权最小的边，知道所有结点都练通了；而克鲁斯卡尔算法则是从边出发，寻找使图连通的权值最小边的方法。算法的实现从人脑到电脑的转

27、变是比较复杂的一件事，要求做到具体到实现该方法的每一个步骤，然后再将每一个步骤通过代码实现。这要求我们要明确各个数据元素和个元素之间的关系，然后才能明确使用算法去调用这些数据。通过本次的课程设计，我对数据结构有了一定的认识，明白了数据结构中数据，数据关系，及对其操作的方法。但同时也发现在自己有很多的不足，在使用语言和如何精炼语言需要进行更多的训练。源代码：#include#includeusingnamespacestd;#defineint_max10000/最大值staticintn=0；/全局变量，判断有权图和无权图staticinto=0；/全局变量，清除BUGstaticintl=0

28、;/全局变量，清除BUG#defineinf9999/最小值的最大值#definemax20/最大顶点个数typedefintVRType,QElemType,Status；typedefcharInfoType,VertexType；/|邻接矩阵|/邻接矩阵定义typedefstructArcCellVRTypeadj；/VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图,则为权值类型InfoType*info；/该弧相关信息的指针ArcCell,AdjMatrixmaxmax；typedefstructVertexTypevexsmax；/顶点向量AdjMatrixarcs

29、；/邻接矩阵intvexnum,arcnum；/图的当前顶点数和弧数MGraph_L；/intlocalvex(MGraph_LG,charv)/返回V的位置inti=0；while(G.vexsi!=v)+i；returni；intcreatMGraph_L(MGraph_L&G)/创建图用邻接矩阵表示charv1,v2；inti,j,w；cout请输入顶点和弧的个数endl；cinG.vexnumG.arcnum；cout输入各个顶点endl；for(i=0；iG.vexnum；+i)cinG.vexsi；for(i=0；iG.vexnum；+i)for(j=0;jG.vexnum;+j)

30、G.arcsij.adj=int_max;G.=NULL;for(intk=0;kG.arcnum;+k)cout输入一条边依附的顶点和权endl；cinvlv2w；/输入一条边依附的两点及权值i=localvex(G,vl)；/确定顶点VI和V2在图中的位置j=localvex(G,v2)；G.arcsij.adj=w；G.arcsji.adj=w；for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj!=1&G.arcsij.adjint_max)n+=1；if(n=l)cout这是一个有权图endl

31、；elsecout这是一个无权图endl；cout图G邻接矩阵创建成功！endl；returnG.vexnum；voidljjzprint(MGraph_LG)/邻接矩阵的输出inti,j；if(n=0)for(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj=int_max)cout0；elsecoutG.arcsij.adj；coutendl；elsefor(i=0；i!=G.vexnum；+i)for(j=0；j!=G.vexnum；+j)if(G.arcsij.adj二二int_max)cout8；elsecoutG.a

32、rcsij.adjadjvex=j；arc-nextarc=gra.verticesi.firstarc;gra.verticesi.firstarc=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout图G邻接表创建成功！endl；return1;voidadjprint(ALGraphgra,MGraph_LG)/邻接表输出inti；for(i=0；i!=gra.vexnum；+i)ArcNode*p；couti,G.vexsi；p=gra.verticesi.firstarc；while(p!=NULL)cout-p-adjvex；p=p-ne

33、xtarc；cout-End；coutendl；/|/队列定义typedefstructQNodeQElemTypedata；structQNode*next；QNode,*QueuePtr；typedefstructQueuePtrfront；/队头指针QueuePtrrear;/队尾指针LinkQueue；/StatusInitQueue(LinkQueue&Q)/初始化队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)；if(!Q.front)return0；/存储分配失败Q.front-next=NULL;return1;StatusEnQu

34、eue(LinkQueue&Q,QElemTypee)/入队，插入元素e为Q的新的队尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)return0;/存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;StatusDeQueue(LinkQueue&Q,QElemType&e)/出队，若队列不空，则删除Q的队头元素,用e返回，并返回真，否则假QueuePtrp;if(Q.front=Q.rear)return0;p=Q.front-next;e=p-data;Q.front-

35、next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return1;StatusQueueEmpty(LinkQueueQ)/判断队为空if(Q.front=Q.rear)return1;return0;/图的遍历intvisitedmax；/访问标记intwe;intfirstadjvex(ALGraphgra,VNodev)/返回依附顶点V的第一个点/即以V为尾的第一个结点if(v.firstarc!=NULL)returnv.firstarc-adjvex；intnextadjvex(ALGraphgra,VNodev,intw)/返回依附顶点V

36、的相对于W的下一个顶点ArcNode*p；p=v.firstarc；while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!=NULL)p=p-nextarc;returnp-adjvex;if(p-adjvex=w&p-nextarc=NULL)return-10;/广度优先遍历voidBFSTraverse(ALGraphgra)inti,e;LinkQueueq;for(i=0;i!=gra.vexnum;+i)visitedi=0;InitQueue(q);for(i=0;i!=gra.vexnum;+i)if(!vi

37、sitedi)visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;EnQueue(q,we);/深度优先遍历intDFS(ALGraphgra,inti)visitedi=1;intwe1;cout=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)DFS(gra,we);we=we1;return1;intDFStra(ALGraphgra)inti,j;for(i=0;i

38、!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);return0;/求连通分量intDFSTraverse_fen(ALGraphgra)inti,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)DFS(gra,j);coutendl;l+;return0;/最小生成树的普利姆算法typedefstructintadjvex;intlowcost;closedge;intMiniSpan

39、Tree_PRIM(intgmax,intn)intlowcostmax,prevexmax；/lowcost存储当前集合分别到剩余结点的最小权值/prevex存储最短路径的前一个结点inti,j,k,min；for(i=2；i二n；i+)/n个顶点，n-1条边lowcosti=g1i；/初始化prevexi=1；/顶点未加入到最小生成树中lowcostl=0；/标志顶点1加入U集合for(i=2；i=n；i+)/形成n-1条边的生成树min=inf；k=0；for(j=2；j=n；j+)/寻找满足边的一个顶点在U,另一个顶点在V的最小边if(lowcostjmin)&(lowcostj!=0)min=lowcostj；k=j；cout(prevexk-1,k-1)min；lowcostk=O；/顶点k加入Ufor(j=2；j0)f=acrvisitedf;returnf;typedefstructacrintpre；/弧的一结点intbak；/弧另一结点intweight；/弧的权edg；voidMiniSpanTR