《图的应用(拓扑排序 求关键路径)》由会员分享，可在线阅读，更多相关《图的应用(拓扑排序 求关键路径)（11页珍藏版）》请在金锄头文库上搜索。
1、实验六图的应用及其实现一、实验目的1进一步功固图常用的存储结构。 2熟练掌握在图的邻接表实现图的基本操作。 3理解掌握AOV 网、AOE 网在邻接表上的实现以及解决简单的应用问题。二、实验内容题目一：从键盘上输入AOV 网的顶点和有向边的信息,建立其邻接表存储结构,然 后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述 AOV 网的类型定义和基本操 作,完成上述功能。 测试数据：教材图 7.28 题目二：从键盘上输入AOE 网的顶点和有向边的信息,建立其邻接表存储结构,输 出其关键路径和关键路径长度。 试设计程序实现上述 AOE网类型定义和基本操作,完成 上述功能。 测试数据：教材图 7.
2、29 三、实验步骤 、数据结构与核心算法的设计描述 基本数据结构：基本数据结构： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedefintStatus; /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等*/ #define INFINITYINT_MAX/定义无穷大 #define MAX_VERTEX_NUM20 typedefintVertexType; typedefintInfoType; typedefstructArcNode/ 表结
3、点定义 InfoType info; intadjvex;/邻接点域，存放与Vi 邻接的点在表头数组中的位置 ArcNode*nextarc;/链域，指示依附于vi 的下一条边或弧的结点， ArcNode;typedefstructVNode/表头结点 intdata;/存放顶点信息 structArcNode*firstarc;/指示第一个邻接点 VNode,AdjListMAX_VERTEX_NUM;typedef struct/图的结构定义 AdjListvertices;/顶点向量intvexnum, arcnum; intIsquan;/是否含有权值 MGraph; typedef
4、struct int*top; int*base; intstacksize; Sqstack; typedefintElemType;Status Initstack(Sqstack if(!s.base) returnERROR; s.top=s.base; s.stacksize=25; returnOK; intindegreeMAX_VERTEX_NUM; intveMAX_VERTEX_NUM;/e 各顶点的最早发生时间 intvlMAX_VERTEX_NUM;/各顶点发生的最晚发生时间 调用的函数调用的函数 StatusStatusStatusStatus Initstack(S
5、qstackInitstack(SqstackInitstack(SqstackInitstack(Sqstack ; ; ;否则返回否则返回否则返回否则返回-1-1-1-1 */*/*/*/ StatusStatusStatusStatus ToopologicalSortToopologicalSortToopologicalSortToopologicalSort (MGraph(MGraph(MGraph(MGraphg)/g)/g)/g)/对图进行拓扑排序，并输出拓扑排序的结果对图进行拓扑排序，并输出拓扑排序的结果对图进行拓扑排序，并输出拓扑排序的结果对图进行拓扑排序，并输出拓扑排序
6、的结果 StatusStatusStatusStatus ToopologicalOrderToopologicalOrderToopologicalOrderToopologicalOrder (MGraph(MGraph(MGraph(MGraphg,Sqstackg,Sqstackg,Sqstackg,Sqstack g; SqstackSqstack T;T; cout #include /* malloc()等*/ #include /* INT_MAX 等*/ #include #include /* exit() */ #define TRUE 1 #define FALSE 0
7、 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedefintStatus; /* Status 是函数的类型,其值是函数结果状态代码，如 OK 等*/ #define INFINITYINT_MAX/定义无穷大 #define MAX_VERTEX_NUM20 typedefintVertexType;开始输入顶点数和边数输入顶点信息创建顶点向量的数组输入弧的信息创建了图的邻接表结束否开始将入度为0 的压入栈栈 是 否 为空弹出栈顶元素，输出结点信息并将其邻 接结点的入度减一，入度为0 的入栈结束typedefintInfoTyp
8、e; typedefstructArcNode/ 表结点定义 InfoType info; intadjvex;/邻接点域，存放与Vi 邻接的点在表头数组中的位置 ArcNode*nextarc;/链域，指示依附于vi 的下一条边或弧的结点， ArcNode;typedefstructVNode/表头结点 intdata;/存放顶点信息 structArcNode*firstarc;/指示第一个邻接点 VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义 AdjListvertices;/顶点向量 intvexnum, arcnum; intIs
9、quan;/是否含有权值 MGraph; intindegreeMAX_VERTEX_NUM; intveMAX_VERTEX_NUM;/e 各顶点的最早发生时间 intvlMAX_VERTEX_NUM;/各顶点发生的最晚发生时间/* 图的邻接表存储(存储结构定义)的基本操作*/ intLocateVex(MGraphG,VertexTypeu) /* 初始条件:图 G 存在,u 和 G 中顶点有相同特征*/ /* 操作结果:若 G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ inti; for(i=0;iG.vexnumG.arcnum; coutG.verticesi.dat
10、a; G.verticesi.firstarc=NULL; coutG.Isquan;if(!G.Isquan) coutvavb; else cinvavbvc; i=LocateVex(G,va); /* 弧尾*/ j=LocateVex(G,vb); /* 弧头*/ p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; if(G.Isquan) p-info=vc; else p-info=0; p-nextarc=G.verticesi.firstarc; /* 插在表头*/ G.verticesi.firstarc=p; returnOK;
11、void Display(MGraph ArcNode *p; cout“adjvex.datanextarc; /system(“pause“); / / /建立栈相关的数据结构和函数/ typedef struct int*top; int*base; intstacksize; Sqstack; typedefintElemType;Status Initstack(Sqstack if(!s.base) returnERROR; s.top=s.base; s.stacksize=25; returnOK; intPush(Sqstack if(!s.base)return0; els
12、e s.top=s.base+s.stacksize; s.stacksize+=10; *s.top=e; s.top+; returnOK; Status Pop(Sqstack e = *-s.top; returnOK; /Pop; intStackEmpty(Sqstacks) /若栈为空栈，则返回 TRUE,否则返回FLASE if(s.top =s.base) return1; else return 0; / void FindDegree(MGraph g,int indegree) /对=图中的各个顶点的入度进行统计，并将第 i 个顶点的入度数放入 indegreeiArc
13、Node *p; inti; for (i=0;inextarc) indegreep-adjvex+; /对图进行拓扑排序，并输出拓扑排序的结果 Status ToopologicalSort (MGraphg) Sqstack s; inti; intcount=0; FindDegree(g,indegree); Initstack(s); for ( i=0;inextarc) intk=p-adjvex; if(!(-indegreek)Push(s,k); if(countnextarc) intk=p-adjvex; if(!(-indegreek) Push(s,k);/将入度
14、为0 的结点压入零入度栈中 if(vei+(p-info)vek) vek=vei+(p-info); if(countnextarc) intk=p-adjvex; intdut=p-info; if(vlk-dutnextarc) intk=p-adjvex; intdut=p-info; intee=vej,el=vlk-dut; cout “g.verticesk.dataendl; returnOK; void main() MGraphg; Sqstack T; cout“创建图:n“;CreateGraph(g); cout“各条弧的信息:n“; Display(g); cout“拓扑排序:n“; ToopologicalSort(g); cout“求关键历经：n“; ToopologicalOrder(g,T); CriticalPath(g,T);
