数据结构实验报告 DFS和BFS算法.doc

（规格为A4纸或A3纸折叠）佛山科学技术学院（用四号宋体）实 验 报 告（用小二号黑体）课程名称 数据结构实验 实验项目 实现DFS和BFS算法 专业班级 姓 名 学 号 指导教师 成 绩 日 期 （用小四号宋体） 一、目的与要求1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历。 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。三、实验步骤1建立图的存储结构。2输入图的基本接点与信息，完成初始化图的工作。3完成图的深度优先搜索（DFS）和广度优先搜索算法，可以采用菜单形式进行显示与选择。（可以在键盘输入边的信息以构建一个无向图。以（a,b）的形式输入边的信息；对此无向图进行深度优先搜索，并输出正确的序列。）4、 源代码#include #include #define Max 20int visitedMax;struct queue/队列的结构体int *head;/指向所申请得到的空间的首地址int *front;/头指针，若队列不为空，指向队列头元素int *rear;/尾指针，若队列不空，指向队列尾元素的下一个位置int stacksize;/当前已分配的存储空间s;/-图的数组存储表示-struct Mgraphchar vexsMax;int arcsMaxMax;int vexnum,arcnum;G;int Locatevex(char v)/确定v在G中的位置int i,t;for(i=0;iG.vexnum;i+)if(G.vexsi=v) t=i;return(t);/-采用数组表示法，构造无向图G-void CreateUDG()int i,j,k;char v1,v2;printf(请输入顶点数和弧数：);scanf(%d,%d,&G.vexnum,&G.arcnum);fflush(stdin);printf(请输入%d个顶点n,G.vexnum);for(i=0;iG.vexnum;i+)printf(请输入顶点%d: ,i);scanf(%c,&G.vexsi);fflush(stdin);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+) G.arcsij=0;printf(请输入%d条弧n,G.arcnum);for(k=0;kG.arcnum;k+)printf(请输入弧%d: ,k);scanf(%c,%c,&v1,&v2);fflush(stdin);i=Locatevex(v1);j=Locatevex(v2);G.arcsij=1;G.arcsji=1;/-返回v的第一个邻接顶点-int Firstadjvex(int v)int i; for(i=0;iG.vexnum;i+)if(G.arcsvi=1) return(i);i=-1;return(i);/-返回v的(相对于w的）下一个邻接顶点-int Nextadjvex(int v,int w)int i;for(i=0;iw) return(i);i=-1;return(i);/-从第v个顶点出发递归地深度优先遍历图G-void DFS(int v) int w;visitedv=1;printf(%c ,G.vexsv);for(w=Firstadjvex(v);w=0;w=Nextadjvex(v,w)if(!visitedw) DFS(w);/-对图G作深度优先遍历-void Dfstraverse()int i;for(i=0;iG.vexnum;i+) visitedi=0;printf(深度优先遍历：);for(i=0;i=s.stacksize)/队列满，追加存储空间s.head=(int *)realloc(s.head,(s.stacksize+10)*sizeof(int);if(!s.head) exit(0);/存储分配失败s.stacksize+=10;*s.rear=e;s.rear+=1;void Dequeue(int u)/若队列不空，则删除s的队头元素u=*s.front;s.front+=1;/-按广度优先非递归遍历图G-void Bfstraverse()int v,u=0,w;for(v=0;vG.vexnum;v+) visitedv=0;Initqueue();printf(广度优先遍历：);for(v=0;v=0;w=Nextadjvex(u,w)if(!visitedw)visitedw=1;printf(%c ,G.vexsw);Enqueue(w);printf(n);void main()int i; printf（*n);printf(1.创图n2.深度优先搜索n3.广度优先搜索n4.退出n); printf(*n);printf(请选择要操作的选项：);scanf(%d,&i);switch(i) case 1:CreateUDG();break;case 2:Dfstraverse();break;case 3:Bfstraverse();break;case 4:exit(0);main();5、 实验结果6、 思考题1图的存储方式有几种？本实验中你会采用什么样的存储方式？答：图的存储方式有数组表示法、邻接表、十字链表、邻接多重表等4种常用存储方式。本实验中我采用了数组表示法存储。 2、给出一幅无向图G如下：V(G)=v1，v2，v3，v4，v5，v6，v7，v8 ，E(G)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)，（v1,v8），（v2,v8）1）请画出示意图；2）请根据你采用的存储方式画出存储图示； 3）在题目2的基础上，请给出图的深度优先搜索序列；v1v4v24）在题目2的基础上，请给出图的广度优先搜索序列。v6 解：（1）v7v3v8v50 1 2 3 4 5 6 70 1 1 0 0 0 0 11 0 0 1 1 0 0 11 0 0 0 0 1 1 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 1 0 0 0 0 01 1 0 0 0 0 0 001234567 v1 v2 v3 v4 v5 v6 v7 v8 (2) (3)深度优先搜索序列：a b d e h c f g (4)广度优先搜索序列：a b c