有向图的深度和广度遍历.doc

青 岛 理 工 大 学数据结构课程实验报告课程名称数据结构班级实验日期2012.5.10姓名实验成绩实验名称有向图的深度和广度遍历实验目的及要求实验目的：1. 学会建立有向图，掌握图的存储结构：邻接表。2. 掌握图的两种遍历方法：深度遍历和广度遍历。实验环境硬件平台：普通的PC机软件平台：Windows7操作系统 编程环境：VisualC+实验内容1. 建立图；2. 利用邻接表，队列存储图的结构；3. 进行图的深度和广度遍历。算法描述及实验步骤/定义存储结构的结构体typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum; ALGraph;/图的结构体typedef int QElemType ; typedef struct QNode QElemType data; QNode *next; QNode,*QueuePtr;/队列的结点结构和指向它的指针 typedef struct LinkQueue QueuePtr front,rear; LinkQueue;/队列的结构体 int LocateVex(ALGraph G,VertexType u)/找出下标 int i; for(i=1;i=G.vexnum;+i) if(u=G.verticesi.data) return i; return 0; void CreateGraph(ALGraph &G)/建立图 int i,j,k; ArcNode *p; VertexType va,vb; printf(请输入图的顶点数,边数: ); scanf(%d,%d,&G.vexnum,&G.arcnum); printf(请输入%d个顶点的值:n,G.vexnum); for(i=1;i=G.vexnum;+i) scanf(%d,&G.verticesi.data); G.verticesi.firstarc=NULL; for(k=1;kadjvex=j; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; void DFS(ALGraph G,int v)/深度遍历逐步找到其中结点 int w; visitedv=1; printf(%d ,G.verticesv.data); for(w=FirstAdjVex(G,G.verticesv.data);w=1;w=NextAdjVex(G,G.verticesv.data,G.verticesw.data) if(!visitedw) DFS(G,w); void DFSTraverse(ALGraph G)/深度遍历 int v; for(v=1;v=G.vexnum;v+) visitedv=0; for(v=1;v=G.vexnum;v+) if(!visitedv) DFS(G,v); printf(n); void BFSTraverse(ALGraph G)/广度遍历，利用队列 int v,u,w; LinkQueue Q; for(v=1;v=G.vexnum;+v) visitedv=0; InitQueue(Q); for(v=1;v=1;w=NextAdjVex(G,G.verticesu.data,G.verticesw.data) if(!visitedw) visitedw=1; printf(%d ,G.verticesw.data); EnQueue(Q,w); printf(n); 调试过程及实验结果总结编程心得：1. 对基础知识的掌握一定要牢固，熟练掌握队列的操作2. 熟练掌握邻接表的结构体3. 熟悉各种操作的算法，根据思路做题。附录#include#include #include #include #include #define INFEASIBLE -1typedef int Status;typedef int Boolean;#define MAX_VERTEX_NUM 21#define NULL 0typedef int VertexType; typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum; ALGraph; int LocateVex(ALGraph G,VertexType u) int i; for(i=1;i=G.vexnum;+i) if(u=G.verticesi.data) return i; return 0; void CreateGraph(ALGraph &G) int i,j,k; ArcNode *p; VertexType va,vb; printf(请输入图的顶点数,边数: ); scanf(%d,%d,&G.vexnum,&G.arcnum); printf(请输入%d个顶点的值:n,G.vexnum); for(i=1;i=G.vexnum;+i) scanf(%d,&G.verticesi.data); G.verticesi.firstarc=NULL; for(k=1;kadjvex=j; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; for( i=1;iadjvex.data ); p=p-nextarc; if (i=G.vexnum) printf(n); int FirstAdjVex(ALGraph G,VertexType v) ArcNode *p; int v1; v1=LocateVex(G,v); p=G.verticesv1.firstarc; if(p) return p-adjvex; else return 0; int NextAdjVex(ALGraph G,VertexType v,VertexType w) ArcNode *p; int v1,w1; v1=LocateVex(G,v); w1=LocateVex(G,w); p=G.verticesv1.firstarc; while(p&p-adjvex!=w1) p=p-nextarc; if(!p|!p-nextarc) return 0; else return p-nextarc-adjvex; Boolean visitedMAX_VERTEX_NUM; void DFS(ALGraph G,int v) int w; visitedv=1; printf(%d ,G.verticesv.data); for(w=FirstAdjVex(G,G.verticesv.data);w=1;w=NextAdjVex(G,G.verticesv.data,G.verticesw.data) if(!visitedw) DFS(G,w); void DFSTraverse(ALGraph G) int v; for(v=1;v=G.vexnum;v+) visitedv=0; for(v=1;vnext=NULL; void DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; void ClearQueue(LinkQueue &Q) QueuePtr p,q; Q.rear=Q.front; p=Q.front-next; Q.front-next=NULL; while(p) q=p; p=p-next; free(q); Status QueueEmpty(LinkQueue Q) if(Q.front-next=NULL) return 1; else return 0; int QueueLength(LinkQueue Q) int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; Status GetHead(LinkQueue Q,QElemType &e) QueuePtr p; if(Q.front=Q.rear) return 0; p=Q.front-next; e=p-data; return 1; void EnQueue(LinkQueue &Q,QElemType e) QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; Status DeQueue(LinkQueue &Q,QElemType &e) QueuePtr p; if(Q.front=Q.rear) return 0; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return 1; void QueueTraverse(LinkQueue Q,void(*vi)(QElemType) QueuePtr p; p=Q.front-next; while(p) vi(p-data); p=p-next; printf(n); void BFSTraverse(ALGraph G) int v,u,w; LinkQueue Q; for(v=1;v=G.vexnum;+v) visitedv=0; InitQueue(Q); for(v=1;v=1;w=NextAdjVex(G,G.ve