数据结构实验八、图的建立和遍历.doc

山东英才职业技工学校实验报告系：_计算机_ 成绩_课程名称_数据结构_实验项目名称_专业班级_学生姓名_学号_一、实验目的1. 理解图的定义。2熟练掌握图的建立,深度优先和广度优先遍历算法的设计与实现。二、实验原理定义图的结构体，建立并初始化一个图，定义深度优先和广度优先遍历算法的函数，设计主函数实现图的建立、深度优先和广度优先遍历过程。三、主要仪器设备或材料 1计算机一台2Vc+编译环境四、实验方法与步骤include #include using namespace std;#define MaxNum 100typedef string VertexType;typedef int EdgeType;struct MGraphVertexType VMaxNum+1;EdgeType EMaxNum+1MaxNum+1;int VisitedMaxNum+1;int n,e;int flag;/1表示有向图，0表示无向图;typedef int DataType;#define MAXQSIZE 100typedef struct DataType dataMAXQSIZE;int front,rear;SqQueue;void InitQueue(SqQueue &Q)Q.front =Q.rear =0;int QueueEmpty(SqQueue &Q)if(Q.front=Q.rear) return 1;else return 0;int QueueFull(SqQueue &Q)if(Q.front=(Q.rear+1)%MAXQSIZE) return 1;else return 0;void EnQueue(SqQueue &Q, DataType e)if( (Q.rear +1)%MAXQSIZE =Q.front ) return;Q.dataQ.rear=e;Q.rear =(Q.rear +1) %MAXQSIZE;void DeQueue(SqQueue &Q, DataType &e)if( Q.front =Q.rear ) return ;e=Q.data Q.front ;Q.front =(Q.front +1)%MAXQSIZE;int FirstAdjVex(struct MGraph G, int u)int i;for(i=1;i=G.n;i+)if(G.Eui=1) return i;return 0;int NextAdjVex(struct MGraph G,int u,int w)int i;for(i=w+1;i=G.n;i+)if(G.Eui=1) return i;return 0;void BFSTraverse(struct MGraph &G,int Starti) int i; int u,w; /开始遍历过程 for(i=1; i=G.n; i+) G.Visitedi = 0; /初始化访问标志 SqQueue Q; InitQueue(Q); /初始化队列 cout广度优先遍历序列如下:endl; if (G.VisitedStarti=0) / 尚未访问 G.VisitedStarti = 1; cout 访问 G.VStartiendl;/ 访问u EnQueue(Q, Starti); / v入队列 while (!QueueEmpty(Q) DeQueue(Q, u);/ 队头元素出队并置为u w=FirstAdjVex(G, u); while( w!=0) if (G.Visitedw=0) / 尚未访问 G.Visitedw=1; cout 访问 G.Vwendl;EnQueue(Q, w); / 访问的顶点w入队列 w=NextAdjVex(G,u,w); void main()struct MGraph G1;int i,j,k;coutG1.n;coutG1.e;coutG1.flag;for(i=1; i=G1.n; i+)cout请输入第iG1.Vi;/初始化邻接矩阵for(i=1;i=G1.n;i+) for(j=1;j=G1.n;j+)G1.Eij=0;/输入边的起点序号和终点序号以及边的权值for(k=1;k=G1.e;k+) cout请输入第ki;cout请输入第kj;G1.Eij=1;if( G1.flag=0 ) G1.Eji=G1.Eij; cout图对应的邻接矩阵如下：endl; for(i=1;i=G1.n;i+)for(j=1;j=G1.n;j+)coutG1.Eij ;coutendl;cout开始遍历过程.endl;int starti