【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下： typedef struct Gnode{ /*邻接表的表结点类型*/ int adivex;/*邻接顶点编号*/ int weight;/*弧上的权值*/ bstmct Gonde*nextare; /*指示下一个弧的结点*/ }Gnode; typedef structAdjlist{ /*邻接表的头结点类型*/ char vdata;/*顶点的数据信息*/ struct Gnode*Firstadj; /*指向邻接表的第1个表结点*/ }Adjlist; typedef struct LinkedWDigraph{/*图的类型*/ int n, e; /*图中顶点个数和边数*/ structAdjlist head;/*指向图中第1个顶点的邻接表的头结点*/ }LinkedWDigraph; 【函数】 int Toplogical(LinkedWDigraph G) { Gnode *p; int j,w,top=0; int *Stack,*ve,*indegree; ve=(int *)mallloc(G.n+1)* sizeof(int)}; indegree=(int *)malloc((G.n+1)*sizeof(int));/*存储网中个顶点的入度*/ Stack=(int *)malloc((G.n+1)*sizeof(int)); /*存储入度为0的顶点的编号*/ if(!ve‖!indegree‖!Stack) exit(0); for(j=1;j＜=G.n;j++){ ve[j]=0; indegree[j]=0; }/*for*/ for(j=1;j＜=G.n;j++){ /*求网中各顶点的入度*/ p=G.head[j].Firstadj; while(p){ {{U}} (1) {{/U}}；p=p-＞nextarc; }/*while*/ }/*for*/ for(i=1;j＜=G.n;j++) /求网中入度为0的顶点并保存其编号*/ if(!indegree[j]) Stack[++top]=j; while(top＞0){ w={{U}} (2) {{/U}}; printf("%c", G.head[w].vdata); p=G.head[w].Firstadj; while(p){ {{U}} (3) {{/U}}; if(!indegree[p-＞adjvex]) Stack[++top]=p-＞adjvex; if({{U}} (4) {{/U}}) ve[p-＞adjvex]=ve[w]+p-＞weight; p=p-＞nextarc; }/*while*/ return{{U}} (5) {{/U}}; }/*Toplogical*/