数据结构实验四图的深度优先与广度优先遍历.doc

天津理工大学实验报告 学院（系）名称：计算机与通信工程学院 姓名 学号 专业 计算机科学与技术 班级 2009级班 2011年5月12日 第5-8节 实验地点 7号楼215 批改意见 成绩 教师签字： 实验四 图的深度优先与广度优先遍历 实验时间：2011年5月12日，12:50 -15:50（地点：7-215） 实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构深度优先遍历、广度优先遍历。1）问题描述：在主程序中提供下列菜单： 1…图的建立 2…深度优先遍历图 3…广度优先遍历图 0…结束 2）实验要求：图的存储可采用邻接表或邻接矩阵；定义下列过程： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图 实验报告格式及要求：按学校印刷的实验报告模版书写。（具体要求见四） 实验思路： 首先，定义邻接矩阵和图的类型，定义循环队列来存储，本程序中只给出了有向图的两种遍历，定义深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的函数，和一些必要的函数，下面的程序中会有说明，然后是函数及运行结果！ #includeiostream #includecstdlib using namespace std; #define MAX_VERTEX_NUM 20//最大顶点数 #define MaxSize 100 bool visited[MAX_VERTEX_NUM]; enum GraphKind{AG,AN,DG,DN};//图的种类，无向图，无向网络，有向图，有向网络 struct ArcNode{ int adjvex; ArcNode * nextarc; }; struct VNode{ int data; ArcNode * firstarc; }; struct Graph{ VNode vertex[MAX_VERTEX_NUM]; int vexnum,arcnum;//顶点数，弧数 GraphKind kind;//图的类型 }; struct SeqQueue{ int *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){//判断循环队列是否满 return (Q.front==(Q.rear+1)%MaxSize)?1:0; } 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.vertex[i].data=i;G.vertex[i].firstarc=NULL; } for(i=0;ie;++i){ cinij;//输入边的信息 ArcNode* s; s= new ArcNode; s-adjvex = j; s-nextarc = G.vertex[i].firstarc; G.vertex[i].firstarc = s; } } void Visit(Graph G,int u) { coutG.vertex[u].data ; } int FirstAdjVex(Graph G,int v){ if(G.vertex[v].firstarc) return G.vertex[v].firstarc-adjvex; else return -1; } int NextAdjVex(Graph G,int v,int w){ ArcNode* p = G.vertex[v].firstarc; while(p-adjvex!=w) p = p-nextarc; i