数学与软件科学学院 实验报告八

《数学与软件科学学院 实验报告八》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学与软件科学学院实验报告一、实验目的及要求：(1)熟练掌握图的邻接矩阵和邻接表的存储方式；2)实现一些基本的图的运算算法(如图的遍历)；(3)掌握常见算法如最小生成树、Top排序树、关键路径、最短路径等应用算法。二、实验内容：、(1)图的基本存储结构和运算算法的实现(必做)；(2)图的遍历算法的实现(选做)；(3)最小生成树的生成算法实现(选做)；(4)Top排序树的算法实现(选做)；(5)关键路径算法的实现(选做)；(6)最短路径算法的实现(选做)。三、实验准备1)计算机设备；2)程序调试环境的准备，如T

2、C环境；3)实验内容的算法分析与代码设计与分析准备。四、实验步骤和实验过程(该部分不够填写.请填写附页)1,对实验问题的描述：用邻接表存储无向图：采用邻接表作为图的存储结构；程序运行时输入图的顶点及边的信息；实现建立图的基本操作；2，算法的数据结构typedefintstatus;typedefstructArcNode{intadjvex;structArcNode*nextarc;ArctexTypeinfo;}ArcNode;typedefcharVertexType[10];statusVisited

3、[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("Enterthenumberofverti

4、cesandedges：：");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dvertices",G->n);for(i=0;in;i++)G->vexs[i]=getchar();for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:",2*(G->e));for(k=0;k<2*(G->e);k++)

5、{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

6、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;jn;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}4，算法描述的程序代码：#include#include#include

7、h>intvisited1[20]={0},visited2[20]={0};typedefstruct{charvexs[20];intedges[20][20];intn,e;}Mgraph;typedefstructQNode{intdata;structQNode*next;intQueusize;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*Q){Q->fron

8、t=Q->rear=(QueuePtr)malloc(sizeof(QNode));Q->front->next=NULL;}voidEnQueue(LinkQueue*Q,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}intDeQueue(Lin