问答题
函数int Toplogical(LinkedWDigraph
G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
typedef struct Gnode{ /*邻接表的表结点类型*/
int adjvex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
struct Gnode*nextarc; /*指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/
}Adjulist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/
}LinkedWDigraph;
例如，某AOE网如图1所示，其邻接表存储结构如图2所示。
图1 AOE网
typedef struct Gnode{ /*邻接表的表结点类型*/
int adjvex; /*邻接顶点编号*/
int weight; /*弧上的权值*/
struct Gnode*nextarc; /*指示下一个弧的结点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头结点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/
}Adjulist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/
}LinkedWDigraph;
例如，某AOE网如图1所示，其邻接表存储结构如图2所示。
图1 AOE网
【正确答案】(1)indegree[p-＞adjvex]++。
(2)Stack[top-]。
(3)indegree[p-＞adjvex]--。
(4)(ve[w]+p-＞weight)＞ve[p-＞adjvex]。
(5)ve[w]。
【答案解析】[解析] 此C语言程序题考点为拓扑排序和关键路径。在解题之前，先了解几个概念。
(1)AVO网络。
一个大工程中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络，图3所示是一个AOV网络。
(2)拓扑排序。
对AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得如在AOV网络中存在一条弧(i,j)，则活动i排在活动j之前。对图3中的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567，01243657，02143657，01243567。
(3)AOE网络。
利用AOV网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为AOE网络。图4所示为一个具有8个活动的某个工程的AOE网络。图中，有6个顶点，分别表示事件V1～V6，其中V1是工程的开始状态，V4是工程的结束状态。边上的权表示完成该活动所需的时间。
(4)关键路径。
在AOE网络中某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图4的AOE网络的关键路径为V1-V2-V6-V4，关键路径长度为80。
了解了上面的这些概念以后，解题就非常容易了。
从程序中的注释可知下段程序的作用是求网中各顶点的入度。
for(j=1;j＜=G.n;j++){
p=G.head[j].Firstadj;
while(p){
{{U}} (1) {{/U}}
p=p-＞nextarc;
}
}
从已知的代码结合邻接表来看，首先p指向了邻接表弟1个结点V1的Firstadj域，然后用while循环遍历了V1的Firstadj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有：
indegree=(int*)malloc((G.n+1)*sizeof(int));/*存储网中各顶点的入度*/
所以第(1)空应填indegree[p-＞adjvex]++。
接下来看第(2)空，第(2)空是给w赋值，接下来是打印第w号结点的数据，这也就意味着w号结点是拓扑排序选出来的结点，所以w必是一个入度为0的结点。然而在此之前已经有程序把所有的入度为0的结点保存在Stack数组中了，而且Stack数组是模拟的一个栈，其控制指针只有top，所以我们应该从Stack中取出栈项元素赋值给w。所以第(2)空填Stack[top-]。注意这里不能用“Stack[-top]”，因为前面有入栈语句“Stack[++top]=j;”。
接下来看下面的程序段。
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;
}
此段程序的作用是：把选出结点所关联的边去掉，即原来V1有到V3的边a1=30和到V2的边a2=10，当V1结点选出以后，a1，a2也要随之消失。这时V3和V2的入度要更新，也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p-＞adjvex]--。第(4)空看起来比较棘手，因为前面没有说明ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定
if {{U}}(4) {{/U}}
ve[p-＞adjvex]=ve[w]+p-＞weight;
的功能是计算关键路径长度。ve的初值最开始都是0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点vx，ve[vx]中存的都是最长路径即可。也就是说，首先选出的是V1，从V1～V2只有一条路径，所以ve[v2]=a2=10，从V1～V3只有一条路径，所以ve[v3]=a1=30。然后选出V2结点，V2选出以后，因为V2～V6有a5=50，所以现在到V6的最长路径为ve[v6]=ve[v2]+a5=60。经过若干步后，当程序选中V3结点时，会产生到V6的另外一条路径V1-V3-V6，这条路径的长度为50，这条路径比现存的路径长度ve[v6]短，所以单纯的更新语句“ve[p-＞adjvex]=ve[w]+p-＞weight”不能正确保存最长路径，为了保证ve中保存的路径最长，应该有判断(ve[w]+p-＞weight)＞ve[p-＞adjvex]。所以第(4)空应该填“(ve[w]+p-＞weight)＞ve[p-＞adjvex]”。
第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢?这一点可以从关键路径的定义着手：“称从开始顶点到结束顶点的最长路径为关键路径”，所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。
(1)AVO网络。
一个大工程中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络，图3所示是一个AOV网络。
[*]
图3 AOE网络图
图3 AOE网络图
(2)拓扑排序。
对AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得如在AOV网络中存在一条弧(i,j)，则活动i排在活动j之前。对图3中的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567，01243657，02143657，01243567。
(3)AOE网络。
利用AOV网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为AOE网络。图4所示为一个具有8个活动的某个工程的AOE网络。图中，有6个顶点，分别表示事件V1～V6，其中V1是工程的开始状态，V4是工程的结束状态。边上的权表示完成该活动所需的时间。
[*]
图4 AOE网络图
图4 AOE网络图
(4)关键路径。
在AOE网络中某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图4的AOE网络的关键路径为V1-V2-V6-V4，关键路径长度为80。
了解了上面的这些概念以后，解题就非常容易了。
从程序中的注释可知下段程序的作用是求网中各顶点的入度。
for(j=1;j＜=G.n;j++){
p=G.head[j].Firstadj;
while(p){
{{U}} (1) {{/U}}
p=p-＞nextarc;
}
}
从已知的代码结合邻接表来看，首先p指向了邻接表弟1个结点V1的Firstadj域，然后用while循环遍历了V1的Firstadj指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有：
indegree=(int*)malloc((G.n+1)*sizeof(int));/*存储网中各顶点的入度*/
所以第(1)空应填indegree[p-＞adjvex]++。
接下来看第(2)空，第(2)空是给w赋值，接下来是打印第w号结点的数据，这也就意味着w号结点是拓扑排序选出来的结点，所以w必是一个入度为0的结点。然而在此之前已经有程序把所有的入度为0的结点保存在Stack数组中了，而且Stack数组是模拟的一个栈，其控制指针只有top，所以我们应该从Stack中取出栈项元素赋值给w。所以第(2)空填Stack[top-]。注意这里不能用“Stack[-top]”，因为前面有入栈语句“Stack[++top]=j;”。
接下来看下面的程序段。
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;
}
此段程序的作用是：把选出结点所关联的边去掉，即原来V1有到V3的边a1=30和到V2的边a2=10，当V1结点选出以后，a1，a2也要随之消失。这时V3和V2的入度要更新，也就是把V3和V2的入度分别减1。所以第(3)空应填indegree[p-＞adjvex]--。第(4)空看起来比较棘手，因为前面没有说明ve是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定
if {{U}}(4) {{/U}}
ve[p-＞adjvex]=ve[w]+p-＞weight;
的功能是计算关键路径长度。ve的初值最开始都是0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点vx，ve[vx]中存的都是最长路径即可。也就是说，首先选出的是V1，从V1～V2只有一条路径，所以ve[v2]=a2=10，从V1～V3只有一条路径，所以ve[v3]=a1=30。然后选出V2结点，V2选出以后，因为V2～V6有a5=50，所以现在到V6的最长路径为ve[v6]=ve[v2]+a5=60。经过若干步后，当程序选中V3结点时，会产生到V6的另外一条路径V1-V3-V6，这条路径的长度为50，这条路径比现存的路径长度ve[v6]短，所以单纯的更新语句“ve[p-＞adjvex]=ve[w]+p-＞weight”不能正确保存最长路径，为了保证ve中保存的路径最长，应该有判断(ve[w]+p-＞weight)＞ve[p-＞adjvex]。所以第(4)空应该填“(ve[w]+p-＞weight)＞ve[p-＞adjvex]”。
第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢?这一点可以从关键路径的定义着手：“称从开始顶点到结束顶点的最长路径为关键路径”，所以最后一个选出结点的ve存放的便是关键路径。所以第(5)空应填ve[w]。