数据结构实验图.doc

图的应用 班级 学号 姓名 一、实验预备知识 1 复习C+中的全局变量的概念。 2 复习图的邻接矩阵和邻接表两种存储方式。二、实验目的 1 掌握图的邻接矩阵和邻接表两种存储方法。2 熟悉图的构造算法，了解实际问题的求解效率与采用何种存储结构与算法有着密切联系。3 掌握图的两种搜索路径的遍历算法。三、实验内容1 创建给定的图，从邻接表和邻接矩阵两种存储方式中选择一种。2 对所创建的图进行深度和广度优先搜索遍历，给出遍历过程中的顶点序列。3 编写一个主函数，将上面函数连在一起，构成一个完整程序。4 将实验源程序调试并运行。四、实验要求所建立的图为：l 用邻接表存储结构时，所创建的单链表以结点的从小到大排列。l 用顶点序号来代替顶点的信息。l 注意标志数组visited 的定义和赋值。l 将顶点1作为起点。五、实验结果给出源程序及输入、输出结果。源程序如下：#include#define MaxVertexNum 20 /定义最大顶点数 typedef char VertexType;int visitedMaxVertexNum;typedef structVertexType vexsMaxVertexNum; /顶点信息int edgesMaxVertexNumMaxVertexNum; /邻接矩阵int n,e; /顶点和边数MGraph;void CreateMGraph(MGraph &G)int i,j,k;cout请输入顶点数和边数G.nG.e;cout请输入顶点信息endl;for(i=0;iG.vexsi;for(i=0;iG.n;i+)for(j=0;jG.n;j+)G.edgesij=0;cout请输入每条边（对应的顶点序号）endl;for(k=0;kij; G.edgesij=1; G.edgesji=1;void DFS_MGraph(MGraph G,int i) /从项点i开始，对图进行深度优先搜索遍历的算法coutG.vexs i ;visitedi=1;int j;for(j=0;jG.n;j+)if(visitedj=0&G.edgesij=1)DFS_MGraph(G,j);void DFSTraverse_MGraph(MGraph G)int i;for(i=0;inext =NULL;/进队算法void Enqueue(int elem,Linkqueue &Q)Lnode *s;s=new Lnode;s-data =elem;s-next =NULL;Q.rear -next =s;Q.rear =s;/出队算法void Dlqueue(int &elem,Linkqueue &Q)Lnode *t;if(Q.front =Q.rear )cout队列为空！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 ;void BFS_MGraph(MGraph G,int i) /从顶点i开始，对图进行广度优先搜索遍历的算法int j,k;Linkqueue Q;Initqueue(Q);coutG.vexs i ;visitedi=1;Enqueue(i,Q);while(Q.front !=Q.rear )Dlqueue(k,Q);for(j=0;jG.n;j+)if(G.edgeskj!=0&!visitedj)coutG.vexsj ; visitedj=1;Enqueue(j,Q); void BFSTraverse(MGraph G) int i;for(i=0;iG.n;i+)if(visitedi=0)BFS_MGraph(G,i);void main()MGraph G;CreateMGraph(G); /创建邻接矩阵图int i;for(i=0;iG.n;i+) /初始化标志数组visitedi=0;cout深度优先遍历结果为:endl;DFSTraverse_MGraph(G); /深度优先搜索 coutendl;for(i=0;iG.n;i+) /初始化标志数组visitedi=0;cout广度优先遍历结果为:endl; BFSTraverse(G); /广度优先搜索 coutendl;六、实验总结1.在此程序中for(k=0;kij; G.edgesij