《数据结构实验四图地深度优先与广度优先遍历》由会员分享，可在线阅读，更多相关《数据结构实验四图地深度优先与广度优先遍历（4页珍藏版）》请在金锄头文库上搜索。
1、WORD格式*理工大学实验报告学院系名称：计算机与通信工程学院*学号专业计算机科学与技术班级2021级 1班实验工程实验四图的深度优先与广度优先遍历课程名称数据构造与算法课程代码实验时间2021年5月12日第5-8节实验地点7 号楼 215批改意见成绩教师签字：实验四图的深度优先与广度优先遍历实验时间：2021年 5 月 12 日， 12:50 -15:50地点： 7-215实验目的： 理解图的逻辑特点；掌握理解图的两种主要存储构造邻接矩阵和邻接表，掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目： 任课教师根据实验大纲自己指定每位同学按下述要*现相应算法：根据从键盘输入的数据创立图
2、图的存储构造可采用邻接矩阵或邻接表，并对图进展深度优先搜索和广度优先搜索1问题描述：在主程序中提供以下菜单：1图的建立2深度优先遍历图3广度优先遍历图0完毕2实验要求：图的存储可采用邻接表或邻接矩阵；定义以下过程：CreateGraph(): 按从键盘的数据建立图DFSGrahp() ：深度优先遍历图BFSGrahp() ：广度优先遍历图实验报告格式及要求：按学校印刷的实验报告模版书写。具体要求见四专业资料整理WORD格式第1页共4页专业资料整理WORD格式实验思路：首先，定义邻接矩阵和图的类型， 定义循环队列来存储， 本程序中只给出了有向图的两种遍历， 定义深度优先搜索和广度优先搜索的函数，
3、 和一些必要的函数， 下面的程序中会有说明，然后是函数及运行结果！#include#includeusing namespace std;#define MAX_VERTEX_NUM 20/ 最大顶点数#define MaxSize 100boolvisitedMAX_VERTEX_NUM;enum GraphKindAG,AN,DG,DN;/ 图的种类，无向图，无向网络， 有向图，有向网络struct ArcNodeint adjvex;ArcNode * nextarc;struct VNodeint data;ArcNode * firstarc;struct GraphVNode ve
4、rtexMAX_VERTEX_NUM;int vexnum,arcnum;/顶点数，弧数GraphKind kind;/ 图的类型;struct SeqQueueint *base;int front,rear;SeqQueue InitQueue()/循环队列初始化SeqQueue Q;Q.base = new int;Q.front=0;Q.rear=0;return Q;void DeQueue(SeqQueue &Q,int &u)/出队操作u = *(Q.base+Q.front);Q.front = (Q.front+1)%MaxSize;int QueueFull(SeqQueu
5、e Q)/判断循环队列是否满return (Q.front=(Q.rear+1)%MaxSize)1:0;专业资料整理WORD格式第2页共4页专业资料整理WORD格式void EnQueue(SeqQueue &Q,int x)/入队操作if(QueueFull(Q)cout队满，入队操作失败！endl;exit(0);*(Q.base+Q.rear) = x;Q.rear = (Q.rear+1)%MaxSize;void CreateDG(Graph & G,int n,int e)/ 初始化邻接表头结点int j;for(int i=0;in;+i)G.vertexi.data=i;G.
6、vertexi.firstarc=NULL;for(i=0;iij;/ 输入边的信息ArcNode* s;s= new ArcNode;s-adjvex = j;s-nextarc = G.vertexi.firstarc;G.vertexi.firstarc = s;void Visit(Graph G,int u)coutG.vertexu.dataadjvex;elsereturn -1;int NextAdjV ex(Graph G,int v,int w)ArcNode* p = G.vertexv.firstarc;while(p-adjvex!=w)p = p-nextarc;i
7、f(p-nextarc)return p-nextarc-adjvex;elsereturn -1;void DFSGrahp(Graph G,int v)visitedv=true;Visit(G ,v);/ 访问顶点 V ，对从未访问过的邻接点w 递归调用 DFS专业资料整理WORD格式第3页共4页专业资料整理WORD格式for(int w=FirstAdjV ex(G,v);w!=0;w=NextAdjV ex(G,v,w)if(!visitedw) DFSGrahp(G ,w);void DFSTraverse(Graph G)/对图 G 做深度优先搜索 for(int v=0;vG.
8、vexnum;+v)visitedv=false;/ 初始化访问标志数组visitedfor(v=0;vG.vexnum;+v)if(!visitedv) DFSGrahp(G,v);/ 对尚未访问的顶点v 调用 DFSvoid BFSGrahp(Graph G)/图的广度优先搜索SeqQueue Q;Q=InitQueue();int u;for(int v=0;vG.vexnum;+v)if(!visitedG ,v)EnQueue(Q,v);/v 入队列while(!(Q.front=Q.rear)1:0)DeQueue(Q,u);/对首元素出队，赋给uvisitedu=true;Visit(G ,u);for(int w=FirstAdjV ex(G,u);w!=0;w=NextAdjV ex(G,u,w)/u 的未访问过的邻接点w 入队列if(!visitedw)EnQueue(Q,w);intmain()Graph p;int n,e;cout输入图的顶点及边数：ne;cout创立图： endl;CreateDG(p,n,e);cout图的优先深度结果为：endl;DFSTraverse(p);cout图的广度优先结果为：endl;BFSGrahp(p);printf( 结果如上所示 !n);return 0;专业资料整理WORD格式第4页共4页专业资料整理
