资源描述：
《图的应用(拓扑排序 求关键路径)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验六图的应用及其实现一、实验目的1．进一步功固图常用的存储结构。2．熟练掌握在图的邻接表实现图的基本操作。3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。二、实验内容[题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列.试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。测试数据：教材图7.28[题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述A
2、OE网类型定义和基本操作,完成上述功能。测试数据：教材图7.29三、实验步骤㈠、数据结构与核心算法的设计描述基本数据结构：#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/#defineINFINITYINT_MAX//定义无穷大∞#defineMAX_VERTEX_NUM20typedefintVertexType;typed
3、efintInfoType;typedefstructArcNode//表结点定义{InfoTypeinfo;intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置ArcNode*nextarc;//链域，指示依附于vi的下一条边或弧的结点，}ArcNode;typedefstructVNode//表头结点{intdata;//存放顶点信息structArcNode*firstarc;//指示第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{
4、//图的结构定义AdjListvertices;//顶点向量intvexnum,arcnum;intIsquan;//是否含有权值}MGraph;typedefstruct{int*top;int*base;intstacksize;}Sqstack;typedefintElemType;StatusInitstack(Sqstack&s){s.base=(int*)malloc(sizeof(int)*25);if(!s.base)returnERROR;s.top=s.base;s.stacksize=2
5、5;returnOK;}intindegree[MAX_VERTEX_NUM];intve[MAX_VERTEX_NUM];//e各顶点的最早发生时间intvl[MAX_VERTEX_NUM];//各顶点发生的最晚发生时间调用的函数StatusInitstack(Sqstack&s)StatusPop(Sqstack&s,int&e)//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；否则返回ERRORintPush(Sqstack&s,int&e)intStackEmpty(Sqstacks)/
6、/若栈为空栈，则返回TRUE,否则返回FLASEStatusCreateGraph(MGraph&G)voidDisplay(MGraph&G)/*输出图G的信息*/voidFindDegree(MGraphg,intindegree[])//对=图中的各个顶点的入度进行统计，并将第i//个顶点的入度数放入indegree[i]intLocateVex(MGraphG,VertexTypeu)/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
7、*/StatusToopologicalSort(MGraphg)//对图进行拓扑排序，并输出拓扑排序的结果StatusToopologicalOrder(MGraphg,Sqstack&T)//拓扑序列StatusCriticalPath(MGraphg,SqstackT)//关键路径㈡、函数调用及主函数设计（可用函数的调用关系图说明）voidmain(){MGraphg;SqstackT;Main函数cout<<"创建图:";CreateGraph(g);创建图cout<<"输出图的信息:";Di
8、splay(g);cout<<"拓扑排序:";ToopologicalSort(g);拓扑排序输出图信息求最小路径cout<<"求关键历经：";ToopologicalOrder(g,T);CriticalPath(g,T);}㈢程序调试及运行结果分析（1）在创建图的过程中需要考虑输入的方便，这就需要标记根据用户选择是否需要输入权值，选择不需要权值时就不会有关权值信息的操作。所以这就在图的结
