《数据结构实验四图的深度优先与广度优先遍历》由会员分享，可在线阅读，更多相关《数据结构实验四图的深度优先与广度优先遍历（6页珍藏版）》请在金锄头文库上搜索。
1、天津理工大学实验报告学院（系）名称：计算机与通信工程学院姓名学号专业计算机科学与技术班级2009级1班实验项目实验四 图的深度优先与广度优先遍历课程名称数据结构与算法课程代码实验时间2011年5月12日 第5-8节实验地点7号楼215批改意见成绩教师签字： 实验四 图的深度优先与广度优先遍历实验时间：2011年5月12日，12:50 -15:50（地点：7-215）实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目：（任课教师根据实验大纲自己指定）每位同学按下述要求实现相应算法： 根据从键盘输入的数据创建图（
2、图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单： 1图的建立 2深度优先遍历图 3广度优先遍历图 0结束2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图实验报告格式及要求：按学校印刷的实验报告模版书写。（具体要求见四）整理为word格式实验思路：首先，定义邻接矩阵和图的类型，定义循环队列来存储，本程序中只给出了有向图的两种遍历，定义深度优先搜索和广度优先搜索的函数，和一些必要的函数，下面的程序
3、中会有说明，然后是函数及运行结果！#include#includeusing namespace std;#define MAX_VERTEX_NUM 20/最大顶点数#define MaxSize 100bool visitedMAX_VERTEX_NUM;enum GraphKindAG,AN,DG,DN;/图的种类，无向图，无向网络，有向图，有向网络struct ArcNodeint adjvex; ArcNode * nextarc;struct VNodeint data; ArcNode * firstarc; struct GraphVNode vertexMAX_VERTEX_
4、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(SeqQueue Q)/判断循环队列是否满r
5、eturn (Q.front=(Q.rear+1)%MaxSize)?1:0;整理为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.vertexi.firstarc=NULL;for(i=0;iij;/输
6、入边的信息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;else return -1;int NextAdjVex(Graph G,int v,int w)ArcNode* p = G.vertexv.firstarc;while(p-adjvex!=w)p = p-nextarc;if(p-nextarc)return p-nextarc-adjvex
7、;else return -1; void DFSGrahp(Graph G,int v)visitedv=true;Visit(G,v);/访问顶点V，对从未访问过的邻接点w递归调用DFS整理为word格式for(int w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw) DFSGrahp(G,w);void DFSTraverse(Graph G)/对图G做深度优先搜索for(int v=0;vG.vexnum;+v)visitedv=false;/初始化访问标志数组visited for(v=0;vG.vexnum;+v)if
8、(!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=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w) /u的未访问过的邻接点w入队列if(!visitedw)EnQueue(Q,w);int main() 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格式
