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

《数据结构实验八、图的建立和遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、山东英才职业技工学校实验报告系：__计算机_____成绩_______________课程名称__数据结构___实验项目名称_______________________________专业班级__________________学生姓名___________________学号____________一、实验目的1.理解图的定义。2．熟练掌握图的建立,深度优先和广度优先遍历算法的设计与实现。二、实验原理定义图的结构体，建立并初始化一个图，定义深度优先和广度优先遍历算法的函数，设计主函数实现图的建立、深度优先和广度优先遍历过程。三、主要仪器设

2、备或材料1．计算机一台2．Vc++编译环境四、实验方法与步骤include#includeusingnamespacestd;#defineMaxNum100typedefstringVertexType;typedefintEdgeType;structMGraph{VertexTypeV[MaxNum+1];EdgeTypeE[MaxNum+1][MaxNum+1];intVisited[MaxNum+1];intn,e;intflag;//1表示有向图，0表示无向图};typedefintDataTy

3、pe;#defineMAXQSIZE100typedefstruct{DataTypedata[MAXQSIZE];intfront,rear;}SqQueue;voidInitQueue(SqQueue&Q){Q.front=Q.rear=0;}intQueueEmpty(SqQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intQueueFull(SqQueue&Q){if(Q.front==(Q.rear+1)%MAXQSIZE)return1;elsereturn0;}voidEnQu

4、eue(SqQueue&Q,DataTypee){if((Q.rear+1)%MAXQSIZE==Q.front)return;Q.data[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}voidDeQueue(SqQueue&Q,DataType&e){if(Q.front==Q.rear)return;e=Q.data[Q.front];Q.front=(Q.front+1)%MAXQSIZE;}intFirstAdjVex(structMGraphG,intu){inti;for(i=1;i<=G.n;i+

5、+)if(G.E[u][i]==1)returni;return0;}intNextAdjVex(structMGraphG,intu,intw){inti;for(i=w+1;i<=G.n;i++)if(G.E[u][i]==1)returni;return0;}voidBFSTraverse(structMGraph&G,intStarti){inti;intu,w;//开始遍历过程for(i=1;i<=G.n;i++)G.Visited[i]=0;//初始化访问标志SqQueueQ;InitQueue(Q);//初始化队列cout<<"

6、广度优先遍历序列如下:"<

7、nQueue(Q,w);//访问的顶点w入队列}w=NextAdjVex(G,u,w);}}}}voidmain(){structMGraphG1;inti,j,k;cout<<"请输入顶点个数:";cin>>G1.n;cout<<"请输入边数：";cin>>G1.e;cout<<"请输入有向/无向标志（1表有向，0表无向）";cin>>G1.flag;for(i=1;i<=G1.n;i++){cout<<"请输入第"<>G1.V[i];}//初始化邻接矩阵for(i=1;i<=G1.n;i++)for(j=1

8、;j<=G1.n;j++)G1.E[i][j]=0;//输入边的起点序号和终点序号以及边的权值for(k=1;k<=G1.e;k++){cout<<"请输入第"<<