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

.\无向图的深度遍历实验报告系别

计算机系

班级

学号

姓名课程名称

数据结构

实验日期实验名称

图的遍历

成绩实验目的：1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在精品文档放心下载邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。感谢阅读实验条件：计算机一台，VisualC++6.0实验内容：1.问题描述以邻接矩阵或邻接表为存储结构， 利用深度优先搜索算法或广度优先搜索算精品文档放心下载法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和精品文档放心下载各连通分量的遍历序列。2.数据结构类型定义采用邻接矩阵为存储结构：typedefstructArcNode{intadj;}ArcNode;//邻接矩阵元素的定义typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];//为顶点的集合ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];感谢阅读intvexnum,arcnum;//vexnum 为顶点数，arcnum为弧数谢谢阅读}AdjMatrix;//邻接矩阵的定义模块划分创建一个无向图以邻接矩阵为存储结构：voidCreateUDN(AdjMatrix*G)谢谢阅读邻接矩阵的定位：intLocateVertex(AdjMatrix*G,VertexDatav)谢谢阅读深度优先遍历：voidDepthFirstSearch(AdjMatrixG,intv)精品文档放心下载无向图的遍历：voidTraverseGraph(AdjMatrixG)精品文档放心下载主函数：voidmain().\详细设计#include<stdio.h>#include<stdlib.h>#include<math.h>#defineOK1#defineERROR0#defineFALSE0#defineTRUE1#defineMAX_VERTEX_NUM100精品文档放心下载intvisited[MAX_VERTEX_NUM];感谢阅读typedefintAdjType;typedefintVertexData;typedefenum{DG,DN,UDG,UDN}GraphKind;精品文档放心下载typedefstructArcNode{AdjTypeadj;}ArcNode;typedefstruct{VertexDatavertex[MAX_VERTEX_NUM];谢谢阅读ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];精品文档放心下载intvexnum,arcnum;}AdjMatrix;intLocateVertex(AdjMatrix*G,VertexDatav)精品文档放心下载{intj=ERROR,k;for(k=0;k<G->vexnum;k++)if(G->vertex[k]==v){j=k;break;}return(j);}32.intGreateUDN(AdjMatrix*G)谢谢阅读{inti,j,k;.\VertexDatav1,v2;printf("输入图的顶点数和弧数：\n");谢谢阅读scanf("%d,%d",&G->vexnum,&G->arcnum);精品文档放心下载getchar();for(i=0;i<G->vexnum;i++){for(j=0;j<G->vexnum;j++)}printf("输入图的顶点：\n");for(i=0;i<G->vexnum;i++){scanf("%d",&G->vertex[i]);感谢阅读47. }for(k=0;k<G->arcnum;k++){printf("输入一条弧的两个顶点：");精品文档放心下载scanf("%d,%d",&v1,&v2);getchar();i=LocateVertex(G,v1);j=LocateVertex(G,v2);}return(OK);}60.61.voidDepthFirstSearch(AdjMatrixG,intv)谢谢阅读{intj;64. printf("%d",G.vertex[v]);精品文档放心下载printf("\n");.\visited[v]=TRUE;for(j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj==1)感谢阅读DepthFirstSearch(G,j);}voidTraverseGraph(AdjMatrixG)感谢阅读72.{ inti;for(i=0;i<G.vexnum;i++)visited[i]=FALSE;感谢阅读for(i=0;i<G.vexnum;i++)75. if(!visited[i]) DepthFirstSearch(G,i);谢谢阅读}intmain(){inti,j;AdjMatrixG;GreateUDN(&G);printf("此无向图的深度遍历为：");TraverseGraph(G);printf("输出邻接矩阵\n");for(i=0;i<G.vexnum;i++){87.for(j=0;j<G.vexnum;j++)88.{89.printf("%d",G.arcs[i][j].adj);90.}91.printf("\n");}return0;}94.测试数据及结果第一组测试：输入数据：顶点：1,2.\预测结果：输出结点数据： 1,2输出邻接矩阵 0110实际结果：第二组测试：输入数据：顶点：0,1,2,3,4预测结果：输出结点数据： 0,1,2,3,4输出邻接矩阵 0111010010100111110100110实际结果：.\第三组测试：输入数据：顶点：0,1,2,3,456预测结果：输出结点数据： 0123456输出邻接矩阵 011110010100