图遍历的演示报告及源代码.pdf

《图遍历的演示报告及源代码.pdf》由会员分享，可在线阅读，更多相关《图遍历的演示报告及源代码.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 1 of 18 题 5.3 图遍历的演示 实习报告 题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作 一、需求分析 1、以邻接多重表为存储结构；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、要求利用栈实现无向图的深度优先遍历；4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；5、用凹入表打印生成树；6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用 C+语言编写，在 Visial C+6.0环境下通过。二、概要设计 1、设定图的抽象数据类型:ADT

2、 Graph 数据对象 V:V 是具有相同特性的数据元素的集合,称为点集.数据关系 R:R=VR VR=(v,w)|v,w 属于 V,(v,w)表示 v 和 w 之间存在的路径 基本操作 P:CreatGraph(&G,V,VR)初始条件:V 是图的顶点集,VR 是图中弧的集合.操作结果:按 V 和 VR 是定义构造图 G.DestroyGraph(&G)初始条件:图 G 存在 操作结果:销毁图 G LocateVex(G,u)初始条件:图 G 存在,u 和 G 中顶点有相同的特征 操作结果:若图 G 中存在顶点 u,则返回该顶点在图中的位置;否则返回其他信息 GetVex(G,v)初始条件:

3、图 G 存在,v 是 G 中顶点 操作结果:返回 v 的值 FirstAjvex(G,v)初始条件:图 G 存在,v 是 G 中顶点 操作结果:返回 v 的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空 NextAjvex(G,v,w)初始条件:图 G 存在,v 是 G 中顶点,w 是 v 的邻接顶点 操作结果:返回 v 的下一个邻接顶点,若 w 是 v 的最后一个邻接顶点,则返回空 DeleteVexx(&G,v)初始条件:图 G 存在,v 是 G 中顶点 操作结果:删除顶点 v 已经其相关的弧 DFSTraverse(G,visit()初始条件:图 G 存在,visit 的顶点的应用函

4、数 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 2 of 18 操作结果:对图进行深度优先遍历,在遍历过程中对每个结点调用 visit 函数一次,一旦 visit 失败,则操作失败 BFSTraverse(G,visit()初始条件:图 G 存在,visit 的顶点的应用函数 操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用 visit 函数一次,一旦 visit 失败,则操作失败 ADT Graph 2、设定栈的抽象数据类型：ADT Stack 数据对象：D=ai|aiCharSet，i=1，2，n，n0 数据关系：R1=|ai-1,aiD,i=2，n 基本操作：

5、InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。Push(&S,e);初始条件：栈 S 已存在。操作结果：在栈 S 的栈顶插入新的栈顶元素 e。Pop(&S,e);初始条件：栈 S 已存在。操作结果：删除 S 的栈顶元素，并以 e 返回其值。StackEmpty(S)初始条件：栈 S 已存在。操作结果：若 S 为空栈，则返回 TRUE，否则返回 FALSE。ADT Stack 3、设定队列的抽象数据类型：ADT Queue 数据对象:D=ai|ai 属于 Elemset,i=1,2.,n,n=0 数据关系

6、:R1=|ai-1,ai属于 D,i=1,2,n 约定 ai 为端为队列头,an 为队列尾 基本操作:InitQueue(&Q)操作结果:构造一个空队列 Q DestryoQueue(&Q)初始条件：队列 Q 已存在。操作结果：队列 Q 被销毁，不再存在。EnQueue(&Q,e)初始条件:队列 Q 已经存在 操作结果:插入元素 e 为 Q 的新的队尾元素 DeQueue(&Q,&E)初始条件:Q 为非空队列 操作结果:删除 Q 的队尾元素,并用 e 返回其值 QueueEmpty(Q)计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 3 of 18 初始条件:队列已经存在 操作结

7、果:若队列为空,则返回 TRUE,否则返回 FLASE ADT Queue 4、本程序包含九个模块：1）主程序模块 void main()手动构造一个图；从文件导入一个图；显示图的信息；进行深度优先遍历图；进行广度优先遍历图；保存图到一个文件；寻找路径；销毁一个图；2）手动构造一个图-自己输入图的顶点和边生成一个图；3）从文件导入一个图；4）显示图的信息-打印图的所有顶点和边；5）进行深度优先遍历图-打出遍历的结点序列和边集；6）进行广度优先遍历图-打出遍历的结点序列和边集；7）保存图到一个文件；8）寻找从起点到终点，但中间不经过某点的所有简单路径；9）销毁图。三、详细设计 1、顶点,边和图类

8、型#define MAX_INFO 10 /*相关信息字符串的最大长度+1*/#define MAX_VERTEX_NUM 20 /*图中顶点数的最大值*/typedef char InfoType;/*相关信息类型*/typedef char VertexType;/*字符类型*/typedef enumunvisited,visitedVisitIf;typedef struct EBox VisitIf mark;/*访问标记*/int ivex,jvex;/*该边依附的两个顶点的位置*/struct EBox *ilink,*jlink;/*分别指向依附这两个顶点的下一条边*/Info

9、Type *info;/*该边信息指针*/EBox;typedef struct VertexType data;EBox *firstedge;/*指向第一条依附该顶点的边*/VexBox;typedef struct 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 4 of 18 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/*无向图的当前顶点数和边数*/AMLGraph;图的基本操作如下：int LocateVex(AMLGraph G,VertexType u)；/查 G 和 u 有相同特征的顶点，若存在则返回该顶点

10、在无向图中位置;否则返回-1。VertexType&GetVex(AMLGraph G,int v)；/以 v 返回邻接多重表中序号为 i 的顶点。int FirstAdjVex(AMLGraph G,VertexType v)；/返回 v 的第一个邻接顶点的序号。若顶点在G 中没有邻接顶点,则返回-1。int NextAdjVex(AMLGraph G,VertexType v,VertexType w)；/返回 v 的(相对于 w 的)下一个邻接顶点的序号若 w 是 v 的最后一个邻接点,则返回-1。void CreateGraph(AMLGraph&G)；/采用邻接多重表存储结构,构造无

11、向图 G。Status DeleteArc(AMLGraph&G,VertexType v,VertexType w)；/在 G 中删除边。Status DeleteVex(AMLGraph&G,VertexType v)；/在 G 中删除顶点 v 及其相关的边。void DestroyGraph(AMLGraph&G)；/销毁一个图 void Display(AMLGraph G)；/输出无向图的邻接多重表G。void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType)；/从 start 顶点起,（利用栈非递归）深度

12、优先遍历图G。void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType)；/从 start 顶点起,广度优先遍历图 G。void MarkUnvizited(AMLGraph G)；/置边的访问标记为未被访问。其中部分操作的伪码算法如下：void CreateGraph(AMLGraph&G)/*采用邻接多重表存储结构,构造无向图 G*/DestroyGraph(G);/*如果图不空,先销毁它*/输入无向图的顶点数 G.vexnum；输入无向图的边数 G.edgenum；输入顶点的信息 IncInfo；依次输入无向图

13、的所有顶点；for(k=0;kmark=unvisited;/*设初值*/耍 p-ivex=i;p-jvex=j;pinfo=NULL;M p-ilink=G.adjmulisti.firstedge;/*插在表头*/G.adjmulisti.firstedge=p;p-jlink=G.adjmulistj.firstedge;/*插在表头*/G.adjmulistj.firstedge=p;void Display(AMLGraph G)/*输出无向图的邻接多重表G*/MarkUnvizited(G);输出无向图的所有顶点；for(i=0;iivex=i)/*边的 i 端与该顶点有关*/if

14、(!p-mark)/*只输出一次*/coutG.adjmulisti.data-jvex.datamark=visited;p=p-ilink;else/*边的 j 端与该顶点有关*/if(!p-mark)/*只输出一次*/coutivex.data-G.adjmulisti.datamark=visited;p=p-jlink;coutendl;void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType)/*从 start 顶点起,深度优先遍历图 G(非递归算法)*/InitStack(S);w=LocateVex(

15、G,start);/*先确定起点 start 在无向图中的位置*/for(v=0;vG.vexnum;v+)Visitedv=0;/*置初值*/for(v=0;v=0;w=NextAdjVex(G,G.adjmulistu.data,G.adjmulistw.data)if(!Visitedw)Push(S,w);DestroyStack(S);/*销毁栈,释放其空间*/void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType)/*从 start 顶点起,广度优先遍历图 G*/for(v=0;vG.vexnum;v+

16、)Visitedv=0;/*置初值*/InitQueue(Q);z=LocateVex(G,start);/*先确定起点 start 在无向图中的位置*/for(v=0;v=0;w=NextAdjVex(G,G.adjmulistu.data,G.adjmulistw.data)if(!Visitedw)Visitedw=1;Visit(G.adjmulistw.data);EnQueue(Q,w);DestroyQueue(Q);/*销毁队列,释放其占用空间*/计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 7 of 18 2、栈类型#define STACK_INIT_SIZ

17、E 100 /*存储空间初始分量*/#define STACKINCREMENT 10 /*存储空间分配增量*/typedef int SElemType;typedef struct SElemType *base;SElemType *top;/*栈顶指针*/int stacksize;SqStack;栈的基本操作如下：Status InitStack(SqStack&S)；/构造一个空栈 S。Status DestroyStack(SqStack&S)；/销毁栈 S(无论空否均可)。Status Push(SqStack&S,SElemType e)；/在 S 的栈顶插入新的栈顶元素 e

18、。Status Pop(SqStack&S,SElemType&e)；/删除 S 的栈顶元素并以 e 带回其值。Status StackEmpty(SqStack S)；/若 S 为空栈，则返回 TRUE，否则返回 FALSE。3、队列类型 typedef int QelemType；typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;/*队头、队尾指针*/LinkQueue;队列的基本操作如下：Status InitQ

19、ueue(LinkQueue&Q)；/构造一个空队列 Q。Status DestroyQueue(LinkQueue&Q)；/销毁队列 Q(无论空否均可)。Status QueueEmpty(LinkQueue Q)；/若 Q 为空队列,则返回 1,否则返回-1。Status EnQueue(LinkQueue&Q,QElemType e)；/插入元素 e 为 Q 的新的队尾元素。Status DeQueue(LinkQueue&Q,QElemType&e)；计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 8 of 18 /若队列不空,删除 Q 的队头元素,用 e 返回其值,并返

20、回 1,否则返回-1。4、生成树类型:typedef struct CSNode VertexType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;/*树的二叉链表(孩子-兄弟)存储结构*/生成树的操作：void DFSTree(AMLGraph G,int v,CSTree&DT)；/从第 v 个顶点出发深度遍历图G,建立以 DT 为根的生成树。void DFSForest(AMLGraph G,VertexType start,CSTree&DT)；/建立图 G 的深度优先生成森林的(最左)孩子(右)兄弟链表 DT。

21、void PrintTraverse(CSTree T)；/打印图 G 的遍历生成树的边。void PrintAllTraverse(CSTree T)/打印图 G 的遍历生成森林的边。void BFSTree(AMLGraph G,int v,CSTree&BT)；/从第 v 个顶点出发广度遍历图G,建立以 BT 为根的生成树。void BFSForest(AMLGraph G,VertexType start,CSTree&BT)；/建立图 G 的广度优先生成森林的(最左)孩子(右)兄弟链表 BT。void PrintCSTree(CSTree T,int i)；/用凹入表方式打印一棵以孩

22、子-兄弟链表为存储结构的树。void PrintCSForest(CSTree T)；/用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森林。其中部分操作的伪码算法如下：void DFSTree(AMLGraph G,int v,CSTree&DT)/*从第 v 个顶点出发深度遍历图G,建立以 DT 为根的生成树*/first=1;Visitedv=1;for(w=FirstAdjVex(G,G.adjmulistv.data);w=0;w=NextAdjVex(G,G.adjmulistv.data,G.adjmulistw.data)if(!Visitedw)p=(CSTree)mallo

23、c(sizeof(CSNode);/*分配孩子结点*/strcpy(p-data,G.adjmulistw.data);p-firstchild=NULL;p-nextsibling=NULL;if(first)/*w是 v 的第一个未被访问的邻接顶点是根的左孩子结点*/DT-firstchild=p;first=0;else /*w是 v 的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 9 of 18 q-nextsibling=p;q=p;DFSTree(G,w,q);/*从第 w 个顶点出发深度优先遍历图 G,建立子生成

24、树 q*/void BFSTree(AMLGraph G,int v,CSTree&BT)/*从第 v 个顶点出发广度遍历图G,建立以 BT 为根的生成树*/r=BT;i=j=0;Visitedv=1;InitQueue(Q);EnQueue(Q,v);/*先把第一个顶点入队列*/while(!QueueEmpty(Q)first=1;DeQueue(Q,u);for(w=FirstAdjVex(G,G.adjmulistu.data);w=0;w=NextAdjVex(G,G.adjmulistu.data,G.adjmulistw.data)if(!Visitedw)Visitedw=1;

25、p=(CSTree)malloc(sizeof(CSNode);strcpy(p-data,G.adjmulistw.data);p-firstchild=NULL;p-nextsibling=NULL;if(first)/*w 是 v 的第一个未被访问的邻接顶点是根的左孩子结点*/r-firstchild=p;first=0;else /*w 是 v 的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/q-nextsibling=p;curi+=p;/*用一个数组指针保存生成树的根*/q=p;EnQueue(Q,w);r=curj+;/*回朔到上一棵生成树的根*/DestroyQueue(

26、Q);void PrintCSTree(CSTree T,int i)/*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树*/计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 10 of 18 for(j=1;j=i;j+)coutendsends;/*留出 i 个空格以表现层*/coutdatafirstchild;p;p=p-nextsibling)PrintCSTree(p,i+1);/*打印子树*/void PrintCSForest(CSTree T)/*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森树*/for(p=T;p;p=p-nextsibling)cout

27、The i+th tree:endl;PrintCSTree(p,0);5、主程序和其他伪码算法 void main()显示菜单；输入功能选择键；switch(flag)case 1:手动构造一个图；case 2:从文件导入一个图；case 3:显示图的信息；case 4:进行深度优先遍历图；case 5:进行广度优先遍历图；case 6:保存图到一个文件；case 7:退出程序；销毁图；int VisitedMAX_VERTEX_NUM;/*访问标志数组(全局量)*/void AllPath(AMLGraph G,VertexType start,VertexType nopass,Vert

28、exType end,int k)/*寻找路径*/Pathk=start;/*加入当前路径中*/l=LocateVex(G,nopass);u=LocateVex(G,start);Visitedu=1;if(start=end)/*找到了一条简单路径*/coutPath0;计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 11 of 18 for(i=1;Pathi;i+)coutPathi;/*打印输出*/cout=0;w=NextAdjVex(G,G.adjmulistu.data,G.adjmulistw.data)if(w=l)continue;/*如果找到那个不想经过的

29、点,就绕过它,相当不执行后面的语句*/if(!Visitedw)temp=G.adjmulistw.data;AllPath(G,temp,nopass,end,k+1);/*继续寻找*/Visitedu=0;Pathk=0;/*回溯*/void SaveGraph(AMLGraph G)/*保存图的信息*/建立输出文件流对象 outgraph；输入文件名 fileName；outgraph.open(fileName,ios:out);连接文件,指定打开方式 if(!outgraph)/*调用重载算符函数测试流*/cerrFile could not be open.endl;abort()

30、;向流插入数据；outgraph.close();/*关闭文件*/void LoadGraph(AMLGraph&G)建立输入文件流对象 ingraph；输入文件名 fileName；if(!ingraph)cerrFile could not be open.endl;abort();向流输出数据；ingraph.close();/*关闭文件*/计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 12 of 18 visit(VertexType v)/*输出结点*/coutvends;return OK;void message()/*菜单显示*/couttt*t1:Creat

31、Graph Manuallyt *n;couttt*t2:Creat Graph From Filet *n;couttt*t3:Dispay The Grapht *n;couttt*t4:BFS The Graphtt *n;couttt*t5:DFS The Graphtt *n;couttt*t6:Save Graph To Filet *n;couttt*t7:Print All Patht *n;couttt*t8:Destroy The Grapht *n;coutB-E-H 3、选择操作 8 销毁图，好继续下一个测试。4、遍历一个非连通的无向图，如遍历以下这个非连通无向图：eq

32、 oac(,A)eq oac(,C)eq oac(,D)eq oac(,B)eq oac(,G)eq oac(,E)eq oac(,F)eq oac(,H)计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 15 of 18 eq oac(,I)1）选择操作 1，分别进行以下操作：Please input the number of G.vexnum(EG.G.vexnum=10):9 Please input the number of G.edgenum(EG.G.edgenum=4):7 Please input the number of IncInfo(0 for none

33、):0 Please intput 9 values of Vexs8(less 3 characters):A B C D E F G H I Please input 7 Edges orderly(interval by space):F I D H D F C G C E A B 2）选择操作 3，输出图的信息如下：This graph has 9 Vexs:A B C D E F G H I This graph has 7 Edges:A-B C-E C-G D-F D-H E-G F-I 3）选择操作 4，输入遍历起点，如 A（也可以输入 B，C）*The result of D

34、FSTraverse*The Node list of DFSTraverse:A B C G E D H F I The Egde collection of DFSTraverse:A-B C-E E-G D-F F-I D-H Press any key to disply the DFSForest The BFSForest of BFSTraverse:The 1th tree:A B The 2th tree:C 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 16 of 18 E G The 3th tree:D F I H 4)选择操作 5，输入遍历起点，如 A

35、（也可以输入 B，C）*The result of BFSTraverse*The Node list of DFSTraverse:A B C E G D F H I The Egde collection of DFSTraverse:A-B C-E C-G D-F F-I D-H Press any key to disply the BFSForest The BFSForest of BFSTraverse:The 1th tree:A B The 2th tree:C E G The 3th tree:D F I H 5)选择操作 7，输入以下信息：Please input the

36、 start nod:C Please input the end nod:E Please input the node you dont want to pass:G All the paths form C to E and dont pass G are:C-E 七、附录 源程序文件名清单：GTraverse.cpp /主程序 GTraverse.exe /可执行文件 GTraverse.OBJ /目标源文件 1.txt /存有连通图信息的文本文档 2.txt /存有非连通图信息的文本文档 八、心得体会 这道题的完成，花了我两个通宵和几个白天时间，因为我在设计这道题的时候，老是要追求完

37、美，本来第一天就完全可以把它的基本遍历功能完成。但觉得那么做意义不大，所以就逐步地增加了许多功能。把本来只能遍历连通图的功能上，改进为可以遍历非连通图，接着再改造为可以输出边集，后来又增加了打印生成树的功能，最后还增加了文件的保存和读取，路径的遍历。最难得是，把原来用 C 语言编写的程序改为用 C+语言编写，虽计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 17 of 18 然编写 C+语言水平有限，但这个程序只是用到 C+那些比较基础和简单的知识，所以对我来说，困雾还不是很大。通过这道设计题,使我更深刻的理解数据结构及其重要作用,对数据结构有了一个新的认识,深刻的认识到数据结构对于我们学习计算机的重要性和其深远但是意义.同时,通过这次课程设计,也加强我的动手能力和思维能犛,可以将自己所学的知识用于实践,这不仅对自己是一次锻炼机会,而且让自己有一种成就感和自豪感耬觉得自己终于可以做出一点有用的东西了。说来也奇怪，虽然连续两个通宵，但觪己在设计这个程序时，却乍会觉得累，也不会觉得困，这几天平均每天是睡不到六个小时，想必是自己对编写程序的兴趣和投入，使得自己顿时间觉得非常有力量。不过,我觉得自己编写程序的一些思路算法和水平还非常有限。所以以后自己还得在C语言和其他语言上下苦功夫。计算机软件技术基础课程设计 图的遍历的演示 龚陈继 Page 18 of 18