问答题
[说明]
函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下。
typedef struct Gnode /* 邻接表的表节点类型 */
int adjvex; /* 邻接顶点编号 */
int weight; /* 弧上的权值 */
struct Gonde*nextare; /* 指示下一个弧的节点 */
Gnode;
typedef struct Adjlist /* 邻接表的头节点类型 */
char vdata; /* 顶点的数据信息 */
struct Gnode*Firstadj; /* 指向邻接表的第一个表节点 */
Adjlist;
typedef struct LinkedWDigraph /* 图的类型 */
struct Adjlist head; /* 指向图中第一个顶点的邻接表的头节点 */
LinkedWDigraph;
例如，某AOE-网如图4-14所示，其邻接表存储结构如图4-15所示。
图4-14 某AOE-网
函数int Toplogical (LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中，图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下。
typedef struct Gnode /* 邻接表的表节点类型 */
int adjvex; /* 邻接顶点编号 */
int weight; /* 弧上的权值 */
struct Gonde*nextare; /* 指示下一个弧的节点 */
Gnode;
typedef struct Adjlist /* 邻接表的头节点类型 */
char vdata; /* 顶点的数据信息 */
struct Gnode*Firstadj; /* 指向邻接表的第一个表节点 */
Adjlist;
typedef struct LinkedWDigraph /* 图的类型 */
struct Adjlist head; /* 指向图中第一个顶点的邻接表的头节点 */
LinkedWDigraph;
例如，某AOE-网如图4-14所示，其邻接表存储结构如图4-15所示。
图4-14 某AOE-网
【正确答案】这是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。
AOE-网(Activity On Edge network，边表示活动的网)是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可以用来估算工程的完成时间。
在AOE-网中，入度为0的顶点为源点，出度为0的顶点为汇点。由于有些活动可以并行地执行，因此从源点到汇点的路径中，长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。
设顶点巧的最早发生时间用ve(j)表示，则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。
ve(j)计算方法为：
AOE-网(Activity On Edge network，边表示活动的网)是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可以用来估算工程的完成时间。
在AOE-网中，入度为0的顶点为源点，出度为0的顶点为汇点。由于有些活动可以并行地执行，因此从源点到汇点的路径中，长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。
设顶点巧的最早发生时间用ve(j)表示，则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。
ve(j)计算方法为：
【答案解析】