算法研究：求解AOE网的关键路径

算法研究：求解AOE网的关键路径2013-08-21 csdn Simba888888前面我们简要地介绍了AOE网和关键路径的一些概念，本文接着对求解关键路径程序的主要函数进行分析。现有一AOE网图如图7-9-4所示，我们使用邻接表存储结构，注意与拓扑排序时邻接表结构不同的地方在于，这里弧表结点增加了weight 域，用来存储弧的权值。

求解事件的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程，因此在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算etv 和拓扑序列列表，我们针对前面讲过的AOV网与拓扑排序的程序进行改进，代码如下

/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */bool TopologicalSort（GraphAdjList GL）{EdgeNode *pe;int i, k, gettop;int top = 0;/* 用于栈指针下标*/int count = 0;/* 用于统计输出顶点的个数*//* 建栈将入度为0的顶点入栈*/int *stack = （int *）malloc（GL->numVertexes * sizeof（int））;for （i = 0; i < GL->numVertexes; i++）if （0 == GL->adjList[i].in）stack[++top] = i;/* 将入度为0的顶点入栈 */top2 = 0;etv = （int *）malloc（GL->numVertexes * sizeof（int））;for （i = 0; i < GL->numVertexes; i++）etv[i] = 0; /* 初始化 */stack2 = （int *）malloc（GL->numVertexes * sizeof（int））;cout << "TopologicalSort ..." << endl;while （top ！= 0）{gettop = stack[top--];cout << GL->adjList[gettop].data << " -> ";count++;/* 输出i号顶点，并计数 */stack2[++top2] = gettop; /* 将弹出的顶点序号压入拓扑序列的栈 */for （pe = GL->adjList[gettop].firstedge; pe; pe = pe->next）{k = pe->adjvex;/* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */if （！（--GL->adjList[k].in））stack[++top] = k;/* 求各顶点事件的最早发生时间etv值 */if （（etv[gettop] + pe->weight） > etv[k]）etv[k] = etv[gettop] + pe->weight;}}cout << endl;if （count < GL->numVertexes）return false;elsereturn true;}