无向图深度遍历邻接矩阵报告

《无向图深度遍历邻接矩阵报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、........无向图的深度遍历实验报告系别计算机系班级学号姓名课程名称数据结构实验日期实验名称图的遍历成绩实验目的：1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验条件：计算机一台，VisualC++6.0实验内容：1.问题描述以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。2.数据结构类型定义采用

2、邻接矩阵为存储结构：typedefstructArcNode{intadj;}ArcNode;//邻接矩阵元素的定义typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];//为顶点的集合ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,arcnum;//vexnum为顶点数，arcnum为弧数.专业学习资料.........}AdjMatrix;//邻接矩阵的定义1.模块划分(1)创建一个无向图以邻接矩阵为存储结

3、构：voidCreateUDN(AdjMatrix*G)(2)邻接矩阵的定位：intLocateVertex(AdjMatrix*G,VertexDatav)(3)深度优先遍历：voidDepthFirstSearch(AdjMatrixG,intv)(4)无向图的遍历：voidTraverseGraph(AdjMatrixG)(5)主函数：voidmain()2.详细设计3.#include4.#include5.#include6.#defineOK1

4、7.#defineERROR08.#defineFALSE09.#defineTRUE110.#defineMAX_VERTEX_NUM10011.intvisited[MAX_VERTEX_NUM];12.typedefintAdjType;13.typedefintVertexData;14.typedefenum{DG,DN,UDG,UDN}GraphKind;15.typedefstructArcNode{16.AdjTypeadj;17.}ArcNode;18.typedefstruct{19.Ve

5、rtexDatavertex[MAX_VERTEX_NUM];20.ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];21.intvexnum,arcnum;22.}AdjMatrix;.专业学习资料.........1.intLocateVertex(AdjMatrix*G,VertexDatav)2.{intj=ERROR,k;3.for(k=0;kvexnum;k++)4.if(G->vertex[k]==v)5.{j=k;break;}6.return(j

6、);7.}8.9.intGreateUDN(AdjMatrix*G)10.{inti,j,k;11.VertexDatav1,v2;12.printf("输入图的顶点数和弧数：");13.scanf("%d,%d",&G->vexnum,&G->arcnum);14.getchar();15.for(i=0;ivexnum;i++)16.{17.for(j=0;jvexnum;j++)18.G->arcs[i][j].adj=FALSE;19.}20.printf("输入图的顶点：")

7、;21.for(i=0;ivexnum;i++)22.{scanf("%d",&G->vertex[i]);23.}24.for(k=0;karcnum;k++)25.{26.printf("输入一条弧的两个顶点：");27.scanf("%d,%d",&v1,&v2);28.getchar();29.i=LocateVertex(G,v1);30.j=LocateVertex(G,v2);31.G->arcs[i][j].adj=1;.专业学习资料.........1.G->arcs[j][

8、i].adj=1;2.}3.return(OK);4.}5.6.7.voidDepthFirstSearch(AdjMatrixG,intv)8.{intj;9.printf("%d",G.vertex[v]);10.printf("");11.visited[v]=TRUE;12.for(j=0;j