第6次-图的应用实验-实验题目与报告书

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：实验六：图的应用实验——求关键路径及其应用班级：网络072学号：510713220姓名：田静评语：成绩：指导教师：朱敏批阅时间：2008年11月17日《数据结构》实验报告-1-图的应用实验报告要求1目的与要求:1）掌握AOE网的邻接表存储结构表示及创建算法的c语言实现；2）理解AOE网的拓扑排序算法(算法7.12)的实现原理及应用；3）掌握AOE网关键路径的计算算法（算法7.13，7.14）及C语言实现与应用；4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告,并按时提交。2实验内容或题目题目：图的应用实验——计算AOE网的关键路径内容：按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图1所示AOE网的关键路径。3实验步骤与源程序#defineINFINITY32768#defineTrue1#defineFalse0#defineError-1#defineNULL0#defineOk1#defineMAX_VERTEX_NUM9图1AOE网876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4《数据结构》实验报告-2-typedefenum{DG,DN,UDG,UDN}GraphKind;typedefintVertexData;typedefstructARCNNODE{intadjvex;intweight;structARCNNODE*nextarc;typedefstructVERTEXNODE{VertexDatadata;ArcNode*firstarc;}VertexNode;typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;GraphKindkind;}AdjList;#includeAdjList.h#includeSTACK.h#includestdio.hintve[MAX_VERTEX_NUM];intVN[9]={3,1,1,1,2,1,1,1,0};intAN[11][2]={1,6,2,4,3,5,4,1,4,1,5,2,6,9,7,7,7,4,8,2,8,4};CreateAdjList(AdjList*G){inti,j;intarc=0;ArcNode*arcn,*pre;G-vexnum=9;《数据结构》实验报告-3-for(i=0;iG-vexnum;i++){G-vertex[i].data=i;G-vertex[i].firstarc=NULL;if(VN[i]0){arcn=(ArcNode*)malloc(sizeof(ArcNode));arcn-nextarc=NULL;arcn-adjvex=AN[arc][0];arcn-weight=AN[arc][1];G-vertex[i].firstarc=arcn;pre=arcn;arc++;for(j=1;jVN[i];j++){arcn=(ArcNode*)malloc(sizeof(ArcNode));arcn-nextarc=NULL;arcn-adjvex=AN[arc][0];arcn-weight=AN[arc][1];pre-nextarc=arcn;pre=arcn;arc++;}}}}printAdjList(AdjList*G){inti,j;intarc=0;ArcNode*arcn;printf(vexnumis%d:,G-vexnum);for(i=0;iG-vexnum;i++){printf(vertex[%d]'sdatais:%d\n,i,G-vertex[i].data);arcn=G-vertex[i].firstarc;while(arcn!=NULL){printf(%d-%d,weight:%d,i,arcn-adjvex,arcn-weight);arcn=arcn-nextarc;}printf(\n);}}《数据结构》实验报告-4-voidFindID(AdjListG,intindegree[MAX_VERTEX_NUM]){inti;ArcNode*p;for(i=0;iG.vexnum;i++)indegree[i]=0;for(i=0;iG.vexnum;i++){p=G.vertex[i].firstarc;while(p!=NULL){indegree[p-adjvex]++;p=p-nextarc;}}/*for*/}intTopoOrder(AdjListG,Stack*T){intcount,i,j,k;ArcNode*p;intindegree[MAX_VERTEX_NUM];StackS;InitStack(T);InitStack(&S);FindID(G,indegree);for(i=0;iG.vexnum;i++)if(indegree[i]==0)Push(&S,i);count=0;for(i=0;iG.vexnum;i++)ve[i]=0;while(!IsEmpty(&S)){Pop(&S,&j);Push(T,j);count++;p=G.vertex[j].firstarc;while(p!=NULL){k=p-adjvex;if(--indegree[k]==0)Push(&S,k);if(ve[j]+p-weightve[k])《数据结构》实验报告-5-ve[k]=ve[j]+p-weight;p=p-nextarc;}}if(countG.vexnum)return(Error);elsereturn(Ok);}intCriticalPath(AdjListG){ArcNode*p;inti,j,k,dut,ei,li;chartag;intvl[MAX_VERTEX_NUM];StackT;if(!TopoOrder(G,&T))return(Error);for(i=0;iG.vexnum;i++)vl[i]=ve[G.vexnum-1];while(!IsEmpty(&T)){Pop(&T,&j);p=G.vertex[j].firstarc;while(p!=NULL){k=p-adjvex;dut=p-weight;if(vl[k]-dutvl[j])vl[j]=vl[k]-dut;p=p-nextarc;}}for(j=0;jG.vexnum;j++){p=G.vertex[j].firstarc;while(p!=NULL){k=p-adjvex;dut=p-weight;ei=ve[j];li=vl[k]-dut;tag=(ei==li)?'*':'';printf(%d,%d,%d,%d,%d,%c\n,G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);《数据结构》实验报告-6-p=p-nextarc;}}return(Ok);}intmain(){AdjListG;CreateAdjList(&G);printAdjList(&G);CriticalPath(G);return0;}#includemalloc.h#defineOVERFLOW-1#defineOK0#defineERROR1#defineTRUE1#defineFALSE0#defineSTACK_INIT_SIZE1000#defineSTACKINCREMENT10typedefintSElemType;typedefintStatus;typedefstructSTACK{SElemType*base;SElemType*top;intstacksize;}Stack;typedefstructSTACKSqStack;typedefstructSTACK*pSqStack;StatusInitStack(SqStack*S);StatusDestroyStack(SqStack*S);StatusClearStack(SqStack*S);StatusStackEmpty(SqStack*S);intStackLength(SqStack*S);SElemTypeGetTop(SqStack*S);StatusPush(SqStack*S,SElemTypee);StatusPop(SqStack*S,SElemType*e);StatusInitStack(SqStack*S){S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));《数据结构》实验报告-7-if(!S-base)return(OVERFLOW);S-top=S-base;S-stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack*S){free(S-base);returnOK;}StatusClearStack(SqStack*S){S-top=S-base;returnOK;}StatusIsEmpty(SqStack*S){if(S-top==S-base)returnTRUE;elsereturnFALSE;}intStackLength(SqStack*S){inti;SElemType*p;i=0;p=S-top;while(p!=S-base){p++;i++;}returni;}SElemTypeGetTop(SqStack*S){if(S-top==S-base)returnERROR;return*(S-top-1);}《数据结构》实验报告-8-StatusPush(SqStack*S,SElemTypee){*(S-top++)=e;returnOK;}StatusPop(SqStack*S,SElemType*e){if(S-top==S-base)returnERROR;*e=*(--(S-top));returnOK;}4测试数据与实验结果（可以抓图粘贴）5结果分析与实验体会在对图遍历时，对于连通图，无论是广度优先还是深度优先搜索，仅需要调用一次搜索过程，即从任一顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连同分量中的顶点集。在图的应用问题中，常常需要找从一个顶点到另一个顶点的简单路径，即路径中的顶点均不相同。由于遍历过程将走遍图中的所有顶点，故可以在深度（或广度）优先搜索算法的基础上加以适当的条件，就能得到求解此问题的算法，因此可以将此问题看成是有条件的图遍历过程。有向图在工程计划和经营管理中有着广泛的应用。通常用有向图来表示工程计划有两种方法：一是用顶点表示活动，用有向弧表示活动间的优先关系。另一种是用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。学习本节，我学到了很多，了解了图通性问题，有向无环图的应用，最短路径问题，但也有很多模糊的地方，在以后的学习中我会加以改进。