实验六图的应用及其实现一、实验目的1．进一步功固图常用的存储结构。

2．熟练掌握在图的邻接表实现图的基本操作。

3．理解掌握AOE网在邻接表上的实现及解决简单的应用问题。

二、实验内容[题目]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。

试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。

三、实验步骤（一）、数据结构与核心算法的设计描述本实验题目是基于图的基本操作以及邻接表的存储结构之上，着重拓扑排序算法的应用，做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。

（二）、函数调用及主函数设计以下是头文件中数据结构的设计和相关函数的声明：typedef struct ArcNode // 弧结点{int adjvex;struct ArcNode *nextarc;InfoType info;}ArcNode;typedef struct VNode //表头结点{VertexType vexdata;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct //图的定义{AdjList vertices;int vexnum,arcnum;int kind;}MGraph;typedef struct SqStack //栈的定义{SElemType *base;SElemType *top;int stacksize;}SqStack;int CreateGraph(MGraph &G);//AOE网的创建int CriticalPath(MGraph &G);//输出关键路径（三）、程序调试及运行结果分析（四）、实验总结在做本实验的过程中，拓扑排具体代码的实现起着很重要的作用，反复的调试和测试占据着实验大量的时间，每次对错误的修改都加深了对实验和具体算法的理解，自己的查错能力以及其他各方面的能力也都得到了很好的提高。

最终实验结果也符合实验的预期效果。

四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单：创建AOE网模块：int CreateGraph(MGraph &G) //创建有向网{int i,j,k,Vi,Vj;ArcNode *p;cout<<"\n请输入顶点的数目、边的数目"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;++i){ G.vertices[i].vexdata=i; G.vertices[i].firstarc=NULL;} for(k=0;k<G.arcnum;++k){cout<<"请输入第"<<k+1<<"条边的始点："; cin>>Vi;cout<<"请输入第"<<k+1<<"条边的终点："; cin>>Vj;i=Vi; j=Vj;i--; j--;p=(ArcNode *)malloc(sizeof(ArcNode));if(!p){ cout<<"Overflow!"; return (ERROR); }p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=NULL;G.vertices[i].firstarc=p;cout<<"请输入第"<<k+1<<"条边的权值：";cin>>p->info;}return (OK);}输出关键路径模块：int ve[MAX_VERTEX_NUM]; //存储事件的最早可能发生时间int vl[MAX_VERTEX_NUM]; //存储事件的最迟允许开始时间int InitStack(SqStack &S) //初始化栈{S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ cout<<"初始化栈失败!"; return(ERROR); }S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}int Push(SqStack &S,SElemType e) //压栈{if(S.top-S.base>S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT *sizeof(SElemType)));if(!S.base){ cout<<endl<<"Overflow!"; return(ERROR); }S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return(OK);}int Pop(SqStack &S,SElemType &e) //弹出栈{if(S.top==S.base){cout<<"栈满 !"; return(ERROR); }e=*--S.top;return(OK);}int StackEmpty(SqStack S) //判断栈是否为空{if(S.top==S.base) return (YES);else return(NO);}void FindInDegree(MGraph G,int *indegree) //求各个顶点的入度{int i;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++)while(G.vertices[i].firstarc){indegree[G.vertices[i].firstarc->adjvex]++;G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}int TopologicalOrder(MGraph G,SqStack &T) //拓扑排序{int indegree[MAX_VERTEX_NUM];int i,count=0,j,k;ArcNode *p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i]) Push(S,i); //入度为0的顶点入栈InitStack(T);for(i=0;i<=G.vexnum-1;i++) ve[i]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j); ++count;for(p=G.vertices[j].firstarc; p; p=p->nextarc){ k=p->adjvex;if(!(--indegree[k])) Push(S,k);if(ve[j]+p->info>ve[k]) ve[k]=ve[j]+p->info;}}if(count<G.vexnum) return(ERROR) ;else return(OK);}int CriticalPath(MGraph &G) //输出关键路径函数{int i,j,k,dut;int ee,el;char tag;ArcNode *p;SqStack T;if(!TopologicalOrder(G,T)) return(ERROR);for(i=0;i<=G.vexnum-1;i++)vl[i]=ve[G.vexnum-1];while(!StackEmpty(T)){for(Pop(T,j),p=G.vertices[j].firstarc; p; p=p->nextarc){k=p->adjvex;dut=p->info;if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}}for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc; p; p=p->nextarc){k=p->adjvex; dut=p->info;ee=ve[j]; el=vl[k]-dut;tag=(ee==el)?'*':' ';if(tag=='*')cout<<"V"<<j+1<<"->V"<<k+1<<" "<<"活动最早可能开始时间"<<ee<<" 最迟允许开始时间"<<el<<" "<<endl;}}。