图的基本操作实验报告.doc

《图的基本操作实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图的基本操作实验报告PB12001046向禹1.题目要求及其分析建立一个图，将图进行初始化，通过输入图的结点信息构建图的邻接链表，对图的结构进行深度和广度优先遍历，由此构建图的最小生成树。要求：输入图的各个结点信息建立图的邻接链表，以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列，同时以用户指定的结点为起点，分别利用普利姆算法和克鲁斯卡尔算法求图的最小生成树。2.设计概要首先根据图的存储结构定义图的链表结构（包括顶点关系类型，与弧或边相关的信息，指向下一个结点的指针,图的当前顶点数与边数邻接矩

2、阵等），采用二维数组形式存储图的邻接矩阵，以邻接表来作为图的链式存储结构，每个结点由邻接点域，链域和数据域组成，由此可构造图G。图的深度优先遍历：从某个顶点v出发访问，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到所有与v相邻的顶点都被访问到，若途中尚有顶点未被访问，则另选途中一个未被访问的电作为起始点，重复上述过程直到所有顶点被访问到。图的广度优先遍历：从v出发，依次访问v和v的未被访问的邻接点，然后从这些邻接点出发访问它们的邻接点，直到所有已被访问的顶点的邻接点都被访问到，若尚有未被访问到的顶点，则选取一个顶点重复上述步骤，直到所有顶点被访问到。最

3、小生成树：假设联通网N=（V,{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个分量自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则社区此边额选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。3．详细设计（主要算法步骤描述）typedefstructArcCell{//VRtype是顶点关系类型，对无权图，用1或0VRTypeadj;//表示相邻否；对带权图，则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,

4、AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点输和弧数GraghKindkind;//图的种类标志}Mgragh;StatusCreateUDN(Mgragh&G){//采用数组（邻接矩阵）表示法，构造无向网Gscanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其它信息for(i=0

5、;i的权值if(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相关信

6、息，则输入G.arcs[j][i]=G.arcs[i][j];}returnOK;}typedefstructArcnode{intadjvex;//该弧指向的顶点位置struct*nextarc;//指向下一条弧的指针INfoType*info;//该弧相关信息的指针}Arcnode;typedefstructVnode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList{MAX_VERTEX_NUM};Typedefstruct{AdjListvertices;intv

7、exnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGragh；voidDFS_traverse_Grapg(ALGraphG){//深度优先遍历intv;for(v=0;v

8、*/for(w=0;w