数学与软件科学学院实验报告学期：2011至2012第2学期2012年5月25日课程名称:数据结构专业:信息与计算科学班级2010级6班实验编号：实验八实验项目图的建立与遍历算法实验指导教师冯山姓名：安柯墁学号：2010060601实验成绩：实验八图的建立与遍历算法实验(4学时)*实验目的：(1)熟练掌握图的邻接矩阵和邻接表的存储方式；(2)实现一些基本的图的运算算法(如图的遍历)；(3)掌握常见算法如最小生成树、Top排序树、关键路径、最短路径等应用算法。实验内容：(类C算法的程序实现，任选其二)(1)图的基本存储结构和运算算法的实现(必做)；(2)图的遍历算法的实现(选做)；(3)最小生成树的生成算法实现(选做)；(4)Top排序树的算法实现(选做)；(5)关键路径算法的实现(选做)；(6)最短路径算法的实现(选做)。实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：实验的完整的C程序代码，以及程序实现与结果分析。1,对实验问题的描述：用邻接表存储无向图：采用邻接表作为图的存储结构；程序运行时输入图的顶点及边的信息；实现建立图的基本操作；2，算法的数据结构typedefintstatus;typedefstructArcNode{intadjvex;structArcNode*nextarc;ArctexTypeinfo;}ArcNode;typedefcharVertexType[10];statusVisited[MAC_VERTEX_NUM];typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAC_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}Graph;3，算法基本操作的说明及分析<1>，以邻接表的形式建立图的算法voidCreateMGraph(Mgraph*G){inti,j,k;printf("Enterthenumberofverticesandedges：：\n");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dvertices\n",G->n);for(i=0;i<G->n;i++)G->vexs[i]=getchar();for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:\n",2*(G->e));for(k=0;k<2*(G->e);k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;}}<2>,广度优先搜索算法：voidBFS(MgraphG,inti){intu,j;LinkQueueQ;InitQueue(&Q);printf("%c",G.vexs[i]);visited2[i]=1;EnQueue(&Q,i);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G.n;j++)if(G.edges[i][j]==1&&!visited2[j]){printf("%c",G.vexs[j]);visited2[j]=1;EnQueue(&Q,j);}}}<3>,深度优先搜索算法实现。voidDFSM(Mgraph*G,inti){intj;printf("%c",G->vexs[i]);visited1[i]=1;for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}4，算法描述的程序代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>intvisited1[20]={0},visited2[20]={0};typedefstruct{charv