数据结构课程实验报告课程名称数据结构班级计算123 实验日期2014年6月1日--3日姓名学号实验成绩实验名称实验四图的深度和广度优先遍历实验目的及要求【实验目的】熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。

【实验要求】1.图的存储可采用邻接矩阵或邻接表2.GraphCreate(): 按从键盘的数据建立图3.GraphDFS()：深度优先遍历图4.GraphBFS()：广度优先遍历图5.编写完整程序完成下面的实验内容并上机运行6.整理并上交实验报告实验环境硬件平台：普通的PC机软件平台：Windows 7 操作系统编程环境：VisualC++ 6.0实验内容1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。

算法描述及实验步骤算法：1)定义图的邻接表存储结构2）实现图的邻接表存储，即建立图的存储结构3）实现图的深度优先遍历4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。

利用队列实现图的广度优先遍历。

伪代码：1）定义邻接矩阵和队列的存取结构；2）创建图L：1.置空图L->num=0；2.输入顶点数目num；3.i++,输入结点L->vexs[i]直到L->num;3）输出图L的各顶点；4）深度优先遍历图g中能访问的各个顶点1.输入起点的下标qidian；2.标志数组初始化mark[v]=0;3.for(v=qidian;v<g.num+qidian;v++) //{v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark); //从第v1个点出发深度优先遍历图g中能访问的各个顶点（算法描述里的流程图很详细）}5）广度优先周游图g中能访问的各个顶点。

1.构造空队列；2.入队a[0]；3.a[0]出队，a[0]的邻接点入队，遍历a[0]；4.队首出队，重复3直到队列为空；5.判断是否全遍历完了；6.输出广度优先遍历序列流程图：开始访问V 0,置标志求V 0邻接点有邻接点w求下一邻接点w V 0W 访问过结束NYN YDFS开始标志数组初始化V i =1Vi 访问过DFSV i =V i +1V i ==Vexnums结束NNYY调试过程及实验结果总结本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。

对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。

试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。

只有正确的输入数据，建立图，才能得出正确的遍历结果。

附录#include <stdio.h>typedef int datatype;#define maxsize 1024# define n 100typedef char VEXTYPE;typedef float ADJTYPE;typedef struct{VEXTYPE vexs[n];ADJTYPE arcs[n][n];int num ;}GRAPH;//邻接矩阵数据类型typedef int DA TA TYPE;typedef struct{DATATYPE data[maxsize];int front,rear;}SEQQUEUE;//队列数据类型void GraphInit(GRAPH *L)//置空图L->num=0;}int GraphVexs(GRAPH *L)//求结点数{return(L->num);}void GraphCreate(GRAPH *L)//创建图{int i;GraphInit(L);printf("请输入顶点数目：");scanf("%d",&L->num);printf("请输入各顶点的信息(单个符号）：\n");for(i=0;i<L->num;i++){fflush(stdin);scanf("%c",&L->vexs[i]);}printf("图已经创建完毕！");}void GraphOut(GRAPH L)//图的输出{int i;printf("\n图的顶点数目为：%d",L.num);printf("\n图的各顶点的信息为：\n");for(i=0;i<L.num;i++)printf("%c ",L.vexs[i]);}void DFS(GRAPH g,int qidian,int mark[])//从第qidian个点出发深度优先遍历图g中能访问的各个顶点{int v1;mark[qidian]=1;printf("%c ",g.vexs[qidian]);for(v1=0;v1<g.num;v1++){if(g.arcs[qidian][v1]!=0&&mark[v1]==0)DFS(g,v1,mark);}void GraphDFS(GRAPH g)//深度优先遍历图g中能访问的各个顶点{int qidian,v,v1,mark[maxsize];printf("\n深度优先遍历：");printf("\n请输入起点的下标：");scanf("%d",&qidian);for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark);}}void QueueInit(SEQQUEUE *sq)//建立空队列{sq->front=0;sq->rear=0;}int QueueIsEmpty(SEQQUEUE sq)//判断队列是否为空{if (sq.rear==sq.front)return(1);else return(0);}int QueueFront(SEQQUEUE sq,DATATYPE *e)//保存队头元素{if (QueueIsEmpty(sq)){printf("queue is empty!\n");return 0;}else { *e=sq.data[(sq.front)]; return 1;}}int QueueIn (SEQQUEUE *sq,DATA TYPE x)//把元素x入队尾{if(sq->front==(sq->rear+1)%maxsize){printf("queue is full!\n");return 0;else{sq->data[sq->rear]=x;sq->rear=(sq->rear+1)%maxsize;return(1);}}int QueueOut(SEQQUEUE *sq)//删除队首元素{if(QueueIsEmpty(*sq)){printf("queue is empty!\n");return 0;}else{sq->front=(sq->front+1)%maxsize;return 1;}}void BFS(GRAPH g,int v,int mark[])//从v出发广度优先遍历图g中能访问的各个顶点{int v1,v2;SEQQUEUE q;QueueInit(&q);QueueIn(&q,v);mark[v]=1;printf("%c ",g.vexs[v]);while(QueueIsEmpty(q)==0){QueueFront(q,&v1);QueueOut(&q);for(v2=0;v2<g.num;v2++){if(g.arcs[v1][v2]!=0&&mark[v2]==0){QueueIn(&q,v2);mark[v2]=1;printf("%c ",g.vexs[v2]);}}}void GraphBFS(GRAPH g)//深度优先周游图g中能访问的各个顶点{int qidian,v,v1,mark[maxsize];printf("\n广度优先遍历：");printf("\n请输入起点的下标：");scanf("%d",&qidian);for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)BFS(g,v1,mark);}}void main()//主函数{GRAPH tu;GraphCreate(&tu);GraphOut(tu);GraphDFS(tu);GraphBFS(tu);printf("\n");}。