文献类型：期刊文章

作　　者：王明福[1]

机构地区：[1]深圳职业技术学院软件工程系,深圳518055

出　　处：《计算机工程》

基　　金：粤港关键领域重点突破项目(06KJcd001);深圳职业技术学院科技基金资助项目(03KJc054)

年　　份：2008

卷　　号：34

期　　号：9

起止页码：106-108

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、SCOPUS、UPD、ZGKJHX、核心刊

摘　　要：通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法。该算法扩充图的邻接表的存储结构,使图的存储与算法求解过程共享同一存储空间。从图的源节点开始,用加权取极大运算规则,广度优先递归对图中所有节点进行编码。编码图生成后,利用反向搜索求出从源点到汇点的所有关键路径及长度。该算法比现有算法更简单直观,所需的存储空间更小,算法时间复杂度降低到O(n+e),优于现有算法的O(n2)。

关 键 词：编码图  关键路径  AOE网 广度优先搜索 时间复杂度

分 类 号：TP311.4]