【说明】函数int Toplogical(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE一网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
typedef struct Gnode /*邻接表的表结点类型*/
int adivex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
bstmct Gonde*nextare; /*指示下一个弧的结点*/
Gnode;
typedef struct Adjlist /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第1个表结点*/
Adjlist;
typedef struct LinkedWDigraph /*图的类型*/
int n, e;/*图中顶点个数和边数*/
struct Adjlist 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)
(1) ； p=p-＞nextarc;
/*while*/
/*for*/
for(i=1;j＜=G.n;j++)/求网中入度为0的顶点并保存其编号*/
if(!indegree[j]) Stack[++top]=j;
while(top＞0)
w= (2) ;
printf("%c", G.head[w].vdata);
p=G.head[w].Firstadj;
while(p)
(3) ;
if(!indegree[p-＞adjvex])
Stack[++top]=p-＞adjvex;
if( (4) )
ve[p-＞adjvex]=ve[w]+p-＞weight;
p=p-＞nextarc;
/*while*/
return (5) ;
/*Toplogical*/
参考答案：
(1)indegree[p-＞adjvex]++及其等价形式
此填空在for(j=1;j＜=G.n;j++)中，求网中各顶点的入度。遍历邻接表G.head[j].Firstadj，将每个结点p-＞adjvex的入度indegree[p-＞adjvex]加1。邻接表是j的出度结点表。
(2)Stack[top-]及其等价形式
栈Stack中存放的是入度为0的结点号，此while循环中，w取栈顶值开始搜索打印这些结点。
(3)indegree[p-＞adjvex]--及其等价形式
由于p=G.head[w].Firstadj；因此while循环是遍历这个邻接链表，将每个结点的入度减1。将入度为0的结点号入栈Stack中。
(4)ve[w]+p-＞weight＞ve[p-＞adjvex]及其等价形式
若ve[w]+p-＞weight大于ve[p-＞adjvex]，则ve[w]+p-＞weight是最长路径，用ve[w]+p-＞weight取代ve[p-＞adjvex]。
(5)ve[w]及其等价形式
最终返回的是w结点的ve[w]值作为整个AOE—网的最长路径值。