数据结构实验图

《数据结构实验图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的应用班级学号姓名一、实验预备知识1复习C++中的全局变量的概念。2复习图的邻接矩阵和邻接表两种存储方式。二、实验目的1掌握图的邻接矩阵和邻接表两种存储方法。2熟悉图的构造算法，了解实际问题的求解效率与采用何种存储结构与算法有着密切联系。3掌握图的两种搜索路径的遍历算法。三、实验内容1创建给定的图，从邻接表和邻接矩阵两种存储方式中选择一种。2对所创建的图进行深度和广度优先搜索遍历，给出遍历过程中的顶点序列。3编写一个主函数，将上面函数连在一起，构成一个完整程序。4将实验源程序调试并运行。四、实验要求所建立的图为：l用邻接表存储结构时，所创建的单链表以结点的从小到大排列。l用顶点序

2、号来代替顶点的信息。l注意标志数组visited[]的定义和赋值。l将顶点1作为起点。五、实验结果给出源程序及输入、输出结果。源程序如下：#include#defineMaxVertexNum20//定义最大顶点数typedefcharVertexType;intvisited[MaxVertexNum];typedefstruct{VertexTypevexs[MaxVertexNum];//顶点信息intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵intn,e;//顶点和边数}MGraph;voidCreateMGra

3、ph(MGraph&G){inti,j,k;cout<<"请输入顶点数和边数"<>G.n>>G.e;cout<<"请输入顶点信息"<>G.vexs[i];for(i=0;i>i>>j;G.edges[i][j]=1;G.edges[j][i]=1;}}voidDFS_MGraph(MGraphG,inti)//从项点i

4、开始，对图进行深度优先搜索遍历的算法{cout<

5、r;};//队列的初始化voidInitqueue(Linkqueue&Q){Q.front=Q.rear=newLnode;Q.front->next=NULL;}//进队算法voidEnqueue(intelem,Linkqueue&Q){Lnode*s;s=newLnode;s->data=elem;s->next=NULL;Q.rear->next=s;Q.rear=s;}//出队算法voidDlqueue(int&elem,Linkqueue&Q){Lnode*t;if(Q.front==Q.rear){cout<<"队列为空！"<

6、nt->next==Q.rear)//只有一个结点时{t=Q.front->next;Q.rear=Q.front;Q.front->next=NULL;}else{t=Q.front->next;Q.front->next=t->next;}elem=t->data;}}voidBFS_MGraph(MGraphG,inti)//从顶点i开始，对图进行广度优先搜索遍历的算法{intj,k;LinkqueueQ;Initqueue(Q);cout<

7、eue(k,Q);for(j=0;j