数据结构与算法实验报告-图的深度优先与广度优先遍历(共5页).docx
精选优质文档-倾情为你奉上实验报告学院（系）名称：计算机与通信工程学院姓名学号专业计算机科学与技术班级实验项目实验四：图的深度优先与广度优先遍历课程名称数据结构与算法课程代码实验时间2019年4月26日 第1-2节 实验地点7-219考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。功能完善, 功能不全有小错无法运行正确基本正确有提示无法回答完整较完整一般内容极少无报告有无有无一、实验目的理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。二、实验题目与要求图的遍历 利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。三、 源代码清单=#include<stdlib.h>#define MAX_VERTEX_NUM;typedef int infoType;typedef int vertexType;typedef struct ArcNode int adjvex; struct ArcNode *next; infoType *weight;Arcnode;typedef struct VNode vertexType data; Arcnode *firstarc;VNode;/VNode GMAX_VERTEX_NUM;void getdata(VNode v);/图的创建void createGraph(int n,VNode G) int i,e; Arcnode *p,*q; printf("input the information of the vertexn"); for(i=0;i<n;i+) getdata(Gi); Gi.firstarc=NULL; for(i=0;i<n;i+) printf("create the edges for the %dth vertexn",i); scanf("%d",&e); while(e!=-1) p=(Arcnode *)malloc(sizeof(Arcnode); p->next=NULL; p->adjvex=e; if(Gi.firstarc=NULL) Gi.firstarc=p; else q->next=p; q=p; scanf("%d",&e); /图的遍历(1)-深度优先搜索void DFS(VNode g,int v,int visited) int w; visit(v); visitedv=1; w=FirstAdj(g,v); while(w!=-1) if(visitedw=0) DFS(g,w,visited); w=nextAdj(g,v); void DFSGraph(VNode g,int visited,int n) int i; for(i=0;i<n;i+) visitedi=0; for(i=0;i<n;i+) if(visitedi=0) DFS(g,i,visited); /图的遍历(2)-广度优先搜索void BFS(VNode G,int v,int visited) int w; visit(v); visitedv=1; EnQueue(q,v); while(!emptyA(q) Dequeue(&q,&v); w=FirstAdj(g,v); while(w!=-1) if(visitedw=0) visit(w); EnQueue(q,w); visitedw=1; w=NextAdj(g,v); void Travel_BFS(VNode g,int visited,int n) int i; for(i=0;i<n;i+) visitedi=0; for(i=0;i<n;i+) if(visitedi=0) BFS(g,i,visited); 实验心得： 通过本次实验，我理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。实验中遇到了很多问题，通过与同学交流沟通，最终完成了本次实验，希望以后能再接再厉。专心-专注-专业
