无向图的存储及深度和广度优先遍历

1、数据结构实验报告实验题目:无序图的存储并分别实现深度和广度优先遍历实验目的：理解并掌握以邻接表的方式存储图，以及图的非递归的深度和广度优先遍历实验内容：首先将图的元素输入并以邻接表的方式存储，然后分别进行递归和非递归遍历。 一、需求分析1、输入的形式和输入值的范围：输入图的顶点元素和边；输入数字选择要进行的操作：深度遍历，广度遍历或结束操作。2、输出的形式:按深度或者广度优先顺序输出各节点的编号3、程序所能达到的功能：（1）以邻接表的方式存储图（2）对图进行深度优先的非递归遍历（3）对图进行广度优先的非递归遍历4、测试数据：输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,2

2、 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历；遍历结果为：1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历；遍历结果为：1 3 2 7 6 5 4二 概要设计（1）抽象数据类型定义：#define MaxVerNum 100/边表结点typedef struct nodeint adjvex;struct node *next;EdgeNode,*ENode;顶点表结点；typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode Ad

3、jListMaxVerNum;定义图；typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;（2）主程序的流程：1. 根据提示输入顶点个数和边的个数；2. 输入图的各边； 3. 输入数字执行相关操作（3）其函数之间调用关系如下：main()模块 （开始创建链表）Create（）创建图输入1输入2按广度优先遍历按深度优先遍历 输入0结束操作 执行结束后，重新执行判定操作和循环。三 详细设计1.元素类型#define MaxVerNum 100typedef struct nodeint adjvex;struct node *next;E

4、dgeNode,*ENode;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;2每个模块的分析：（1）主程序模块：int main() int a,v; /创建图Create(G); printf("请选择要进行的操作：n 选择深度优先请输入1；n 选择广度优先请输入2；n结束操作请输入0n"); scanf(&qu

5、ot;%d",&a); while(a!=0) printf("请输入开始遍历顶点的坐标n"); scanf("%d",&v); if(a=1) /深度优先遍历 DfsTravel(G,v); else if(a=2) /广度优先遍历 BfsTravel(G,v); printf("请选择要进行的操作：n 选择深度优先请输入1；n 选择广度优先请输入2；n结束操作请输入0n"); scanf("%d",&a); return 0;（2）深度优先遍历void DfsTravel(Al

6、Graph &G,int v)ENode stackMaxVerNum;ENode p;int visitedMaxVerNum,top=-1,i;for(i=0;i<G.n;i+)visitedi=0; printf("深度优先遍历的结果为：n"); printf("%d ",v);visitedv=1;p=G.adjlistv.firstedge;while(top!=-1|p!=NULL)while(p!=NULL)if(visitedp->adjvex=1)p=p->next;elseprintf("%d &q

7、uot;,p->adjvex);visitedp->adjvex=1;top+;stacktop=p;p=G.adjlistp->adjvex.firstedge;if(top!=-1) p=stacktop; top-; p=p->next;printf("n");（3）广度优先遍历void BfsTravel(AlGraph &G,int v)int visitedMaxVerNum;int queueMaxVerNum;int front=-1,rear=-1; EdgeNode *p; int i; for(i=0;i<G.n;

8、i+)visitedi=0; printf("广度优先遍历的结果为：n");printf("%d ",v);visitedv=1;rear=rear+1;queuerear=v;while(front!=rear) front+;v=queuefront;p=G.adjlistv.firstedge;while(p!=NULL)if(visitedp->adjvex=0)printf("%d ",p->adjvex); visitedp->adjvex=1;rear=rear+1;queuerear=p->ad

9、jvex;p=p->next;printf("n");(4)创建图void Create(AlGraph &G)int i,j,k;EdgeNode *s,*r;printf("请依次输入无向图顶点个数和边的个数n");scanf("%d,%d",&(G.n),&(G.e);getchar();printf("请输入各顶点信息n");for(i=0;i<G.n;i+)scanf("%c",&(G.adjlisti.vertex);getchar();

10、G.adjlisti.firstedge=NULL;printf("请输入各边的信息，输入格式为i,jn"); for(k=0;k<G.e;k+)scanf("%d,%d",&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode);s->adjvex=j;s->next= G.adjlisti.firstedge;G.adjlisti.firstedge=s; r=(EdgeNode*)malloc(sizeof(EdgeNode);r->adjvex=i;r->next= G.adjlistj.firstedge;G.adjlistj.firstedge=r;四 使用说明、测试分析及结果输入各结点元素：a,b,c,d,e,f,g,h；输入图中的各边：1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历；遍历结果为：1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历；遍历结果为：1 3 2 7 6 5 41.程序使用说明；（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入顶点个数和边的个数：2、测试结果与分