图遍历的演示

1、一、 需求分析1. 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。2. 每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。3. (1) 建立无向图G的邻接表表示。按照用户输入顶点数,弧数. 各边(弧尾， 弧头) (2) 输出图中边的表示。用(A,B)表示 (3) 实现无向图的深度优先搜索遍历。实现无向图的广度优先搜索遍历，使用辅助队列q以存储已经被访问的路

2、径长度为1,2,的顶点,并且访问标志数组visited,实现对图的遍历.4. 测试数据：输入图的顶点数和弧数：格式：顶点数，弧数； 输入图的顶点数和弧数：5，4 接着输入各边(弧尾，弧头)： 5，3 3，1 1，2 2，4二、 概要设计1. 抽象数据类型图的定义如下： ADT 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=VR VR=（v,w）|v,wV,(v,w)表示v和w之间存在路径 基本操作P： CreateGraph(&G,V,VR)    初始条件：V是图的顶点集，VR是图中边的集合。   &#

3、160;操作结果：按V和VR的定义构造图G。 DestroyGraph(&G)    初始条件：图G存在。    操作结果：销毁图G。 LocateVex(G,u)    初始条件：图G存在，u和G中顶点有相同特征。    操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 GetVex(G,v)    初始条件：图G存在，v是G中某个顶点。    操作结果：返回v的信息。 FirstEd

4、ge(G,v)    初始条件：图G存在，v是G中某个顶点。    操作结果：返回依附于v的第一条边，若该顶点在G中没有邻接点，则返回“空”。 NextEdge(G,v,w)    初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。    操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。 InsertVex(&G,v)    初始条件：图G存在，v和图中顶点有相同特征。    操

5、作结果：在图G中增添新顶点v。 DeleteVex(&G,v)    初始条件：图G存在，v是G中某个顶点。    操作结果：删除G中顶点v及其相关的边。 2.   主程序 void main( ) 初始化；     用户输入信息:     接受用户输入的信息:     调用各个函数;     输出结果; 3. 本程序共有五个模块

6、 创建图的邻接表表示的模块输出图中边的表示模块深度优先搜索遍历图的模块广度优先搜索遍历图的模块主程序模块三、 详细设计#include <dos.h>#include <conio.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_VERTEX_NUM 20 /图的最大顶点数#define MAXQSIZE 30 /队列的最大容量 enum BOOL False,True;typedef struct ArcNodeint adjvex; /该弧

7、所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode; /弧结点typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一条依附该顶点的弧的指针int vexnum,arcnum; /图的当前顶点和弧数 Graph; typedef struct /队列结构int elemMAXQSIZE; /数据域int front; /队头指针int rear; /队尾指针SqQueue; BOOL visitedMAX_VERTEX_NUM; /全局变量访问标志数组void CreateGraph(Graph

8、&); /生成图的邻接表void DFSTraverse(Graph); /深度优先搜索遍历图void DFS(Graph,int); void BFSTraverse(Graph); /广度优先搜索遍历图void Initial(SqQueue &); /初始化一个队列BOOL QueueEmpty(SqQueue); /判断队列是否空BOOL EnQueue(SqQueue &,int); /将一个元素入队列BOOL DeQueue(SqQueue &,int &); /将一个元素出队列int FirstAdjVex(Graph,int); /求图中

9、某一顶点的第一个邻接顶点int NextAdjVex(Graph,int,int); /求某一顶点的下一个邻接顶点void main()Graph G; /采用邻接表结构的图char j='y'/-编者信息-printf("题目:编制一个“图遍历的演示”的程序.n");printf("班级:信息管理与信息系统01班.n");printf("姓名:徐丽n");printf("学号:201201050635n");printf("完成日期:2014.06.20n");/-/-程序解说

10、-printf("n本程序将演示生成一个图，并对它进行遍历.n");printf("输入图的顶点数和弧数:n格式：顶点数，弧数；例如:5,4n");printf("接着输入各边(弧尾，弧头):n例如:5,3n 3,1n 1,2n 2,4n");printf("程序会生成一个图，并对它进行深度和广度遍历.n");printf("深度遍历:1->2->4->3->5n广度遍历:1->2->3->4->5n");/-while(j!='N'

11、;&&j!='n')printf("n请输入顶点数和弧数：");scanf("%d,%d",&G.vexnum,&G.arcnum); /输入图的顶点数和弧数CreateGraph(G); /生成邻接表结构的图DFSTraverse(G); /深度优先搜索遍历图BFSTraverse(G); /广度优先搜索遍历图printf("图遍历完毕，继续进行吗?(Y/N)");scanf(" %c",&j); void CreateGraph(Graph &G)

12、/构造邻接表结构的图Gint i;int start,end; ArcNode *s;for(i=1;i<=G.vexnum;i+) G.AdjListi=NULL; /初始化指针数组for(i=1;i<=G.arcnum;i+)scanf("%d,%d",&start,&end); /输入弧的起点和终点s=(ArcNode *)malloc(sizeof(ArcNode); /生成一个弧结点s->nextarc=G.AdjListstart; /插入到邻接表中s->adjvex=end;G.AdjListstart=s;s=(Arc

13、Node *)malloc(sizeof(ArcNode);s->nextarc=G.AdjListend;s->adjvex=start;G.AdjListend=s;void DFSTraverse(Graph G)/深度优先遍历图Gint i;printf("深度优先遍历:");for(i=1;i<=G.vexnum;i+) visitedi=False; /访问标志数组初始化for(i=1;i<=G.vexnum;i+)if(!visitedi) DFS(G,i); /对尚未访问的顶点调用DFSprintf("bb n")

14、;void DFS(Graph G,int i)/从第i个顶点出发递归地深度遍历图Gint w;visitedi=True; /访问第i个顶点printf("%d->",i);for(w=FirstAdjVex(G,i);w>0;w=NextAdjVex(G,i,w)if(!visitedw) DFS(G,w); /对尚未访问的邻接顶点w调用DFSvoid BFSTraverse(Graph G)/按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visitedint i,u,w;SqQueue Q; printf("广度优先遍历:")

15、;for(i=1;i<= G.vexnum;i+) visitedi=False; /访问标志数组初始化Initial(Q); /初始化队列for(i=1;i<=G.vexnum;i+)if(!visitedi)visitedi=True; /访问顶点iprintf("%d->",i);EnQueue(Q,i); /将序号i入队列while(!QueueEmpty(Q) /若队列不空，继续DeQueue(Q,u); /将队头元素出队列并置为ufor(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w)if(!visit

16、edw) /对u的尚未访问的邻接顶点w进行访问并入队列visitedw=True;printf("%d->",w);EnQueue(Q,w);printf("bb n");int FirstAdjVex(Graph G,int v)/在图G中寻找第v个顶点的第一个邻接顶点if(!G.AdjListv) return 0;else return(G.AdjListv->adjvex);int NextAdjVex(Graph G,int v,int u)/在图G中寻找第v个顶点的相对于u的下一个邻接顶点ArcNode *p;p=G.AdjLis

17、tv;while(p->adjvex!=u) p=p->nextarc; /在顶点v的弧链中找到顶点uif(p->nextarc=NULL) return 0; /若已是最后一个顶点，返回0else return(p->nextarc->adjvex); /返回下一个邻接顶点的序号void Initial(SqQueue &Q) /队列初始化Q.front=Q.rear=0; BOOL QueueEmpty(SqQueue Q)/判断队列是否已空，若空返回True,否则返回Falseif(Q.front=Q.rear) return True;else r

18、eturn False;BOOL EnQueue(SqQueue &Q,int ch)/入队列，成功返回True，失败返回Falseif(Q.rear+1)%MAXQSIZE=Q.front) return False;Q.elemQ.rear=ch;Q.rear=(Q.rear+1)%MAXQSIZE;return True;BOOL DeQueue(SqQueue &Q,int &ch)/出队列,成功返回True，并用ch返回该元素值，失败返回Falseif(Q.front=Q.rear) return False;ch=Q.elemQ.front;Q.front=(Q.front+1)%MAXQSIZE;return True; /成功出队列，返回True四、 调试分析2. 当进行图中边的表示输出时, 目的要验证输入的边是否正确表示, 但在程序中 是用指向顶点的指针表示, 结果只显示出各个顶点的顶点编号, 后来调用邻接表 的数组的顶点数据表示, 正常输出. 3.  进行有向图的广度优先搜索时, 开始只是简单定义一个数组和两个头尾指针, 在进行 数组插入与删除时候只是移动一下头尾的指针,产生了错误, 后来改