洛阳理工学院数据结构实验报告.doc

《洛阳理工学院数据结构实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、洛阳理工学院实验报告系部计算机与信息工程系班级学号姓名课程名称数据结构实验日期2014.4.23实验名称实验5：图的遍历的实现成绩实验目的：掌握图的邻接矩阵和邻接表两种存储结构，掌握图的深度优先和广度优先两种遍历算法。实验条件：电脑一台，VC++6.0实验内容与步骤：内容：采用邻接表存储方式创建一个图，并对该图分别进行深度和广度优先遍历，输出遍历结果。算法思想：1.在数组中查找顶点。2.建立有向网。3.图深度优先搜索4.图的遍历函数，在遍历图的函数中调用深度优先算法函数。5.在主函数中调用创建图和遍历图的函数，完成对图的深度优先遍历运行结果：实验总结：通

2、过此次的实验，让我对图的深度优先收索有所了解，对图的函数功能也进一步的掌握，也对图的结构有进一步的认识；但同时发现自己对图掌握的还远远不够，会出很多错误，仍需努力。附：源程序：#include#include#defineMAX_VERTEX_NUM20/*最多顶点个数*/#defineINFINITY32767/*表示极大值*/#defineTrue1#defineFalse0#defineError-1#defineOK1intvisited[MAX_VERTEX_NUM];/*访问标志数组*//*图的种类：DG

3、表示有向图，DN表示有向网，UDC表示无向图，UDN表示无向网*/typedefenum{DG,DN,UDC,UDN}GraphKind;typedefcharVertexData;/*假设顶点数据为字符型*/typedefstructArcNode{intadj;/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/charinfo;}ArcNode;typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];/*顶点向量*/ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM

4、];/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/}AdjMatrix;AdjMatrixG;voidDepthFirstSearch(AdjMatrixg,intv0);intLocateVertex(AdjMatrix*G,VertexDatav)/*求顶点位置函数*/{intj=Error,k;for(k=0;kvexnum;k++){if(G->vertex[k]==v){j=k;break;}}returnj;}intCreatDN(AdjMatrix*G)/*

5、创建一个有向网*/{inti,j,k,weight;VertexDatav1,v2;printf("输入图的弧数和顶点数，中间用逗号隔开");scanf("%d,%d",&G->arcnum,&G->vexnum);/*输入图的顶点数和弧数*/for(i=0;ivexnum;i++)/*初始化邻接矩阵*/for(j=0;jvexnum;j++)G->arcs[i][j].adj=INFINITY;for(i=0;ivexnum;i++){printf("输入图的顶点");fflush(stdin);scanf("%c",&

6、G->vertex[i]);/*输入图的顶点*/}for(k=0;karcnum;k++){printf("输入一条弧的两个顶点及权值，中间用逗号隔开");/*输入一条弧的两个顶点及权值*/fflush(stdin);scanf("%c,%c,%d",&v1,&v2,&weight);i=LocateVertex(G,v1);j=LocateVertex(G,v2);G->arcs[i][j].adj=weight;/*建立弧*/}return(OK);}/*用邻接矩阵实现深度优先搜索*///intvisited[MAX_VERTEX_NUM

7、];/*访问标志数组*/voidDepthFirstSearch(AdjMatrixg,intv0){intvj;printf("%c",g.vertex[v0]);visited[v0]=True;for(vj=0;vj

8、vi=0;vi