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

《图遍历的演示报告及源代码.docx》由会员分享，可在线阅读，更多相关《图遍历的演示报告及源代码.docx（25页珍藏版）》请在三一办公上搜索。

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

2、 ADT 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) 初始条件: 图G存在,v是G中顶点 操

3、作结果:返回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的顶点的应用函数 Page 1 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 操作结

4、果: 对图进行深度优先遍历,在遍历过程中对每个结点调用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 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始

5、条件：栈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 数据关系:R1=|ai-1,ai属于D,i=1,2,n 约定ai为端为队列头,an为队列尾 基本操作: InitQueue

6、(&Q) 操作结果:构造一个空队列Q DestryoQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 EnQueue(&Q,e) 初始条件:队列Q已经存在 操作结果:插入元素e为Q的新的队尾元素 DeQueue(&Q,&E) 初始条件:Q为非空队列 操作结果:删除Q的队尾元素,并用e返回其值 QueueEmpty(Q) Page 2 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 初始条件:队列已经存在 操作结果:若队列为空,则返回TRUE,否则返回FLASE ADT Queue 4、本程序包含九个模块： 1）主程序模块 void main 手动

7、构造一个图； 从文件导入一个图； 显示图的信息； 进行深度优先遍历图； 进行广度优先遍历图； 保存图到一个文件； 寻找路径； 销毁一个图； ； 2）手动构造一个图-自己输入图的顶点和边生成一个图； 3）从文件导入一个图； 4）显示图的信息-打印图的所有顶点和边； 5）进行深度优先遍历图-打出遍历的结点序列和边集； 6）进行广度优先遍历图-打出遍历的结点序列和边集； 7）保存图到一个文件； 8）寻找从起点到终点，但中间不经过某点的所有简单路径； 9）销毁图。 三、详细设计 1、顶点,边和图类型 #define MAX_INFO 10 /* 相关信息字符串的最大长度+1 */ #define MA

8、X_VERTEX_NUM 20 /* 图中顶点数的最大值*/ typedef char InfoType; /*相关信息类型*/ typedef char VertexType; /* 字符类型 */ typedef enumunvisited,visitedVisitIf; typedef struct EBox VisitIf mark; /* 访问标记 */ int ivex,jvex; /* 该边依附的两个顶点的位置 */ struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */ InfoType *info; /* 该边信息指针 */ EBo

9、x; typedef struct VertexType data; EBox *firstedge; /* 指向第一条依附该顶点的边 */ VexBox; typedef struct Page 3 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)； /采用邻接多重表存储结构,构造无向图G。 Status Delet

11、eArc(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顶点起,深度优先遍历图G。 void BFSTraver

12、se(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； 依次输入无向图的所有顶点； for(k=

13、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端与

14、该顶点有关 */ if(!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(非递归算法)*/

15、InitStack(S); w=LocateVex(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

16、顶点起,广度优先遍历图G*/ for(v=0;vG.vexnum;v+) 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 6 of 18 计算机软

17、件技术基础课程设计 图的遍历的演示 龚陈继 2、栈类型 #define STACK_INIT_SIZE 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)； /销毁

18、栈S(无论空否均可)。 Status Push(SqStack &S,SElemType e)； /在S的栈顶插入新的栈顶元素e。 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 Queu

19、ePtr front; QueuePtr rear; /* 队头、队尾指针 */ LinkQueue; 队列的基本操作如下： Status InitQueue(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,QEl

20、emType &e)； Page 7 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 /若队列不空,删除Q的队头元素,用e返回其值,并返回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 DF

21、SForest(AMLGraph G,VertexType start,CSTree &DT)； /建立图G的深度优先生成森林的(最左)孩子(右)兄弟链表DT。 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)

22、； /建立图G的广度优先生成森林的(最左)孩子(右)兄弟链表BT。 void PrintCSTree(CSTree T,int i)； /用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树。 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.dat

23、a);w=0; w=NextAdjVex(G,G.adjmulistv.data,G.adjmulistw.data) if(!Visitedw) p=(CSTree)malloc(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的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/ q-next

24、sibling=p; Page 8 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 q=p; DFSTree(G,w,q); /*从第w个顶点出发深度优先遍历图G,建立子生成树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=FirstAdjV

25、ex(G,G.adjmulistu.data);w=0; w=NextAdjVex(G,G.adjmulistu.data,G.adjmulistw.data) if(!Visitedw) Visitedw=1; 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的其他未被访问的邻接顶点是

26、上一邻接顶点的右兄弟结点*/ q-nextsibling=p; curi+=p; /*用一个数组指针保存生成树的根*/ q=p; EnQueue(Q,w); r=curj+; /*回朔到上一棵生成树的根*/ DestroyQueue(Q); void PrintCSTree(CSTree T,int i) /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树*/ for(j=1;j=i;j+) coutendsends; /*留出i个空格以表现层*/ coutdatafirstchild;p;p=p-nextsibling) PrintCSTree(p,i+1); /*打印子树*/ void

27、 PrintCSForest(CSTree T) /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森树*/ for(p=T;p;p=p-nextsibling) coutThe 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 V

28、isitedMAX_VERTEX_NUM; /*访问标志数组(全局量) */ void AllPath(AMLGraph G,VertexType start,VertexType nopass,VertexType end,int k) /*寻找路径*/ Pathk=start; /*加入当前路径中*/ l=LocateVex(G,nopass); u=LocateVex(G,start); Visitedu=1; if(start=end) /*找到了一条简单路径*/ coutPath0; for(i=1;Pathi;i+) coutPathi; /*打印输出*/ cout=0; w=Ne

29、xtAdjVex(G,G.adjmulistu.data,G.adjmulistw.data) if(w=l) continue; /*如果找到那个不想经过的点,就绕过它,相当不执行后面的语句*/ 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

30、,ios:out);连接文件,指定打开方式 if(!outgraph) /*调用重载算符函数测试流*/ cerrFile could not be open.endl; abort; 向流插入数据； outgraph.close; /*关闭文件*/ void LoadGraph(AMLGraph &G) 建立输入文件流对象ingraph； 输入文件名fileName； if(!ingraph) cerrFile could not be open.endl; abort; 向流输出数据； ingraph.close; /*关闭文件*/ visit(VertexType v) /*输出结点*/

31、coutvends; Page 11 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 return OK; void message /*菜单显示*/ couttt*t1:Creat 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 A

32、ll Patht *n; couttt*t8:Destroy The Grapht *n; couttt*t9:Exitttt *n; 四、调试分析 1、本程序以邻接多重表为存储结构。这个程序涉及到图的生成和图的深度以及广度遍历,文件的保存和读取，还有栈和队列的操作，另外还有森林的生成和打印，路径的寻找。 2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了方便显示和理解，现在暂且用一个大写字母表示一个顶点。边还可以附加信息，但为了方便操作，暂且不输入信息。已经先把图的相关信息保存在了文本文档里，所以要测试时直接从文件导入，可以减少用手输入的麻烦，同时也可以减少输入的错误。

33、3、由于构造图时，后输入的边是插在先输入的边的前面。所以在输入边时，可以按字母从大到小的顺序输入。那么显示图的时候就可以按字母从小到大的顺序显示。 4、程序定义了一个二倍顶点长的数组存放输入的边，以便程序可以把它保存到文件里。故耗费了一定的内存空间。 五、用户手册 1、本程序的运行环境DOS操作系统，GTraverse.exe 2、进入演示程序后即显示一个有功能选择的界面，如下： 3、选择操作1：程序就提示分别输入无向图的顶点数，边数，边的信息，顶点和边的值： 输入完成后，程序提示按任一键返回菜单： 4、选择操作2：程序提示输入一个存有图信息文件的路径去导入一个图： 如果导入成功，它会显示导入

34、成功，并提示按任一键返回。 5、选择操作3：程序显示图的顶点和边的信息。 6、选择操作4：系统提示输入遍历图的起始点，程序运行后，首先显示深度优先遍历的访问结点序列和生成树的边集。然后再提示按任一键继续显示深度优先遍历的生成森林。 7、选择操作5：系统提示输入遍历图的起始点，程序运行后，首先显示广度优先遍历的访问结点序列和生成树的边集。然后再提示按任一键继续显示广度优先遍历的生成森林。 8、选择操作6：程序会提示输入要存放图信息的文件的路径： 9、选择操作7：程序会提示输入路径遍历的起点start，终点end，不想经过的点nopass。 10、选择操作8：销毁一个图。 11、选择操作9：退出程

35、序。 六、测试结果 1、数据可以任意输入,但是顶点数不要太多，不然占用太多内存，会导致死机。 2、遍历一个连通的无向图，如遍历以下这个连通无向图： eq oac(,A) Page 12 of 18 计算机软件技术基础课程设计 图的遍历的演示 龚陈继 eq oac(,B) eq oac(,C) eq oac(,D) eq oac(,E) eq oac(,F) eq oac(,G) eq oac(,H) 选择操作1，分别进行以下操作： Please input the number of G.vexnum (EG. G.vexnum=10): 8 Please input the number o

36、f G.edgenum (EG. G.edgenum=4): 9 Please input the number of IncInfo (0 for none): 0 Please intput 8 values of Vexs8(less 3 characters): A B C D E F G H Please input 9 Edges orderly(interval by space): F G E H D H C G C F B E B D A C A B 2) 选择操作3，输出图的信息如下： This graph has 8 Vexs: A B C D E F G H This

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