关键路径的可视化实现

杨晓波，陈邦泽，张 环

（1.西藏民族学院 信息工程学院，陕西 咸阳 712082；2.西藏民族学院 教育学院，陕西 咸阳 712082）

AOE网（Activity on edge network）是用边表示活动的网，它是一个带权的有向无环图，其中顶点表示事件（event），弧表示活动（Activity），权表示活动持续的时间。只有当以顶点为头的弧所表示的活动都完成时，顶点所代表的事件才能发生。通常AOE网能够清楚地表明那些在其他工作开始前必须完成的活动，可用来估算工程的完成时间。由于整个工程只有一个开始点和一个完成点，所以在无环的情况下，网中只有一个入度为零的顶点（源点）和一个出度为零的顶点（汇点）。关键路径就是在网络中寻找最长路径，它反映了整个项目完成所需要的最短时间，关键路径由关键活动组成。所谓关键活动就是最晚开始时间和最早开始时间的差为零的活动，也就是说关键活动不能延期。AOE网中的关键路径就是从开始事件到结束事件的最长路径［1］。

文献［2］的算法不需要进行拓扑排序，算法执行效率也有所提高，但存储结构比较复杂，采用的是十字链表，需要对图作3次广度优先遍历，可以输出所有关键活动，但不能把所有的关键路径输出。文献［3］利用图的广度优先搜索与动态规划算法相结合的方法求解关键路径，存储结构采用邻接表形式，不用作拓扑排序，比起传统算法提高了效率，但是该算法不能找出可能的关键路径。前面2种算法均是结构化程序设计的。文献［4］提出了基于面向对象求关键路径的方法，可以求出所有可能路径和关键路径。

本文基于分组拓扑排序序列实现了有向无环图（DAG）［5］的绘制，并将其运用于AOE网关键路径的求解，用面向对象方法实现了求出所有可能路径和所有关键路径，并实现了关键路径的可视化。与文献［4］相比较不需要用户事先将顶点图转换为活动图。

1 AOE网的可视化

1.1 一般图的可视化

假设图中有n个顶点，采用圆形布局法可视化图：以绘图区域的中心为圆心，绘图区域宽度的一半为半径得到一个圆周，将圆周等分为n份得到n个坐标作为图的顶点的坐标，如果两顶点构成一条边则调用drawEdge方法画线，对于网图在两顶点连线五分之二处标出边上的权值，如图1所示系统自动绘制图，实现图的可视化。

图1 图的可视化

1.2 分组拓扑序列绘制有向无环图

由于图2所示的 AOE（Activity－on－Edge）网用圆形布局法绘制的图其顶点的前趋后继关系基本上无法看出来，，所以这种绘制方法不适合于AOE网。可通过扫描图形等方式采用模式识别方法来输入图，但是模式识别对箭头的识别还不理想，而且识别算法的计算量也很大，所以也不适合。因此本文提出一种基于分组拓扑排序［6］序列绘制有向无环图的方法。

图2 AOE网

方法如下：分组拓扑序列将顶点分成group组，因此将绘图区域（宽width，高height）沿x轴方向分group＋1份，取wd＝width／（group＋1），第i组顶点的横坐标x设定为wd×（i＋1），设每组顶点个数为vi；沿y轴方向分为vi＋1份，取hd＝height／（vi＋1），第i组的第j个顶点的纵坐标y设定为hd×（j＋1），这样有向无环图中所有顶点的坐标就设定好了。绘制结果如图3所示。

1.3 具体实现

采用广度优先遍历BFSTraverse算法绘制图，与广度优先遍历不同的是在绘制弧时不能判断顶点的Visited值，否则有的弧就会画不出来。广度优先遍历要用到队列数据结构，设计一个队列类class CQueue

图3 分组拓扑排序序列绘制AOE网

2 关键路径的可视化

2.1 算法建模

系统总共设计4个类，Vertex用来表示顶点，Activity表示活动，Graph类基于Vertex代表顶点构成的整个图，Cgraph类基于Activity代表活动构成的整个图。

2.2 数据准备

人机交互输入数据，输入每个活动的始点arcTail、终点arcHead、活动名称act和活动持续时间duration。由于终点arcHead为始点arcTail的后继顶点，所以将arcHead添加到arcTail的后继动态数组nearVertex中，同时终点arcHead的入度inDegree加1。为避免用户输入数据工作的枯燥和降低输入错误，始点和终点的输入用2个comboBox提供顶点名称供用户选择。另外在输入过程中要防止形成环，系统在窗口右侧放置了一个listBox用于显示用户输入的活动信息，以便用户对照及防止输入回路（见图4）。

图4 人机交互输入数据

所有活动输入结束时，由于顶点的前趋后继关系已确定，活动之间的前趋后继关系不需要用户的干预，可由已知信息直接获得：若活动act［i］.arcHead等于活动act［j］.arcTail，则活动act［i］为前趋，act［j］为后继。

2.3 关键路径的求解

关键路径的求解我们采用文献［4］提出的关键路径法（Critical Path Method，CPM）。为了方便求解，当有多个开始活动和多个结束活动时增加一个虚拟开始活动和一个虚拟结束活动。如此关键路径就是从开始活动到结束活动的最长路径。

从开始活动出发深度优先遍历找出从开始活动到达结束活动的所有路径，存放在动态数组allPath中，并在列表框lstOutputAllPath中一一显示；再对所有路径进行累加比较计算出最长路径长度；将所有最长路径（关键路径）存放在动态数组theCriticalPath中；并将关键路径上的活动标记为关键活动。

2.4 关键路径的输出

在所有关键路径theCriticalPath中取出一条关键路径criticalPath，将关键路径criticalPath上的关键活动逐个取出，在列表框lstOutputCriticalPath中显示，并在pictureBox3上进行绘制。不同的关键路径用不同的颜色绘制。

如图5所示，左边窗口列出所有路径和所有关键路径，右边窗口在AOE网上以不同颜色标出所有关键路径。

图5 用不同颜色标出所有关键路径

3 结束语

传统的关键路径求解算法需要分别求出所有事件的最早开始时间和最晚开始时间，以及每项活动的最早结束时间和最晚结束时间［7－8］，方法复杂比较难理解。关键路径法在项目管理领域得到了广泛的应用和发展［9－12］。本文首先对有向无环图进行分组拓扑排序，然后利用分组拓扑排序序列为顶点分配了可视化坐标，实现了有向无环图的绘制，并将其运用于AOE网关键路径的求解和显示，用面向对象方法实现了求出所有可能路径和所有关键路径，并实现了关键路径的可视化。实验表明：方法简单可靠，更符合人们的思维习惯，形象、直观。

（References）

［1］严蔚敏，吴伟民.数据结构［M］.C语言版.北京：清华大学出版社，1997：183－185.

［2］徐凤生.一种新的关键路径求解算法［J］.计算机应用与软件，2005，22（6）：97－99.

［3］刘芳，王玲.基于动态规划思想求解关键路径的算法［J］.计算机应用，2006，26（6）：1140－1142.

［4］徐长盛，谢立.关键路径算法的面向对象解决［J］.计算机应用研究，2005（4）：96－98.

［5］AndrasfaiB.图论导引［EM］.郭照人，译.北京 ：高等教育出版社，1980.

［6］杨晓波.分组拓扑排序的面向对象实现［J］.福建电脑，2007（5）131.

［7］陈本林，陈佩佩.数据结构［M］.南京：南京大学出版社，1998：148－151.

［8］王明福.一种求解关键路径的新算法［J］.计算机工程，2008，34（9）：106－108.

［9］Gido J，Clements J P.Successful Project Management［M］.Ohio，USA：South－Western College Publishing，1999.

［10］Hiller F S，Liberman G J.Introduction to Operations Research［M］.New York，USA：McGraw－Hill，2001.

［11］Hartmann S，Briskorn D.A Survey of Variants and Extensions of theResource－constrained Project Scheduling Problem［J］.European Journal of Operational Research（S0377－2217），2010，207（1）：1－14.

［12］Lionel G.Quantitative Risk Analysis for Project Management：A Critical Review ［R］／／ Rand Working Paper，（WR－112－RC），2004.Santa Monica，USA：Rand，2004.