实验四图的应用深度优先／广度优先有哪些信誉好的足球投注网站遍历.doc

华北水利水电学院 数据结构 实验报告 2012～2013学年 第 一 学期 2010级 计算机科学与技术 专业 班级： 201013432 学号： 201013432 姓名： 蔡启林 实验四 图的应用 实验题目： 图的应用——深度优先／广度优先有哪些信誉好的足球投注网站遍历 实验内容： 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先有哪些信誉好的足球投注网站遍历操作。 要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先有哪些信誉好的足球投注网站遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现） 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先有哪些信誉好的足球投注网站遍历，并输出遍历的结果。 三、程序源代码： #includeiostream.h #define max 100 int visited[max]; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[max]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct QNode { char data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; int InitQueue(LinkQueue Q) { Q.front=Q.rear=new QNode; if(!Q.front)return 0; Q.front-next=NULL; return 1; } int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } int EnQueue(LinkQueue Q,char e) { QNode *p; p=new QNode; if(!p)return 0; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return 1; } char DeQueue(LinkQueue Q,int e) { QNode *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; delete(p); return 1; } int LocateVex(ALGraph G,int v) { int i; for(i=0;v!=G.vertices[i].dataiG.vexnum;i++) if(i=G.vexnum) return -1; return i; } void CreatGraph(ALGraph G) { int k,i,j; ArcNode *p,*q; cout请输入顶点总数：; cinG.vexnum; cout请输入边数：; cin G.arcnum; char v1,v2; cout输入顶点信息：; for(i=0;iG.vexnum;i++) { cinG.vertices[i].data; G.vertices[i].firstarc=NULL; } cout请输入边的信息endl; for(k=0;kG.arcnum;k++) { cinv1v2; i=LocateVex(G,v1); j=LocateVex(G,v2); p=new ArcNode; q=new ArcNode; p-adjvex=j; p-nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; q-adjvex=i; q-nextarc=G.vertices[j].firstarc; G.vertices[