b11050311欧阳斌图遍历

《b11050311欧阳斌图遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、洛阳理工学院实验报告系别计算机系班级B110503学号B11050311姓名欧阳斌课程名称数据结构实验日期4.28实验名称图的存储结构与遍历算法应用成绩实验目的：熟悉掌握图、连通图的概念与特点，理解与掌握图的邻接矩阵、邻接表存储结构，掌握与应用图的深度优先搜索算法与广度优先搜索算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，VisualC++6.0实验内容：1.【问题描述】利用图的深度优先搜索算法或广度优先搜索算法判断一个图是否为连通图。若不是连通图，说明该图有几个连通分量并给出构成各连通分量的结点序列。2.【测试数据】例如输入如下的图有六个顶点，四条路径。预期输出

2、第一个连通分量ABDF第二个连通分量CE这不是一个连通图，它有两个连通分量。3.【数据结构】typedefenum{DG,DN,UDC,UDN}GraphKind;typedefstructArcNode{intadj;}ArcNode;typedefstruct{charvexs[MAX];//顶点向量ArcNodearcs[MAX][MAX];intvexnum,arcnum;GraphKindkind;}AdjMatrix;3.【算法思想】采用邻接矩阵作为图的存储方式，采用深度优先搜素的方式对图进行遍历，设置一个访问标志数组，根据数组的值，判断整个图是否为连通图，如果不连通，从新的结

3、点遍历，并输出每个连通分量中的元素。1、创建一个网CreateDN(AdjMatrix*G)。2、访问网TraverseGraph(AdjMatrixg)。3、深度优先搜索函数DepthFirstSearch(AdjMatrixg,intv0)。4、定位函数LocateVertex(AdjMatrix*G,charv)。5、输出函数visit(AdjMatrix*G,inti)。源程序#include"stdio.h"#defineTrue1#defineFalse0#defineError-1#defineOK1#defineMAX20#defineINFINITY32768intvis

4、ited[MAX]={False};/*访问标志数组*/inti=1;typedefenum{DG,DN,UDC,UDN}GraphKind;typedefstructArcNode{intadj;}ArcNode;typedefstruct{charvexs[MAX];//顶点向量ArcNodearcs[MAX][MAX];intvexnum,arcnum;GraphKindkind;}AdjMatrix;/*用邻接矩阵法创建有向网的算法如下：*/voidvisit(AdjMatrix*G,inti){printf("%c",G->vexs[i]);G->vexs[i]=1;}intLo

5、cateVertex(AdjMatrix*G,charv)/*求顶点位置函数*/{intj=Error,k;for(k=0;kvexnum;k++)if(G->vexs[k]==v){j=k;break;}return(j);}intCreateDN(AdjMatrix*G)/*创建一个有向网*/{inti,j,k,weight;charv1,v2;printf("输入图的顶点数和弧数");fflush(stdin);scanf("%d,%d",&G->vexnum,&G->arcnum);/*输入图的顶点数和弧数*/for(i=0;ivexnum;i++)/*初始化邻

6、接矩阵*/for(j=0;jvexnum;j++)G->arcs[i][j].adj=INFINITY;for(i=0;ivexnum;i++){printf("输入图的顶点");fflush(stdin);scanf("%c",&G->vexs[i]);/*输入图的顶点*/}for(k=0;karcnum;k++){printf("输入一条弧的两个顶点及权值(权值为1)");fflush(stdin);scanf("%c,%c,%d",&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/i=LocateVertex(G,v1);j=Loca

7、teVertex(G,v2);G->arcs[i][j].adj=weight;/*建立弧*/}return(OK);}voidDepthFirstSearch(AdjMatrixg,intv0){intvj;visit(&g,v0);visited[v0]=True;for(vj=0;vj