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

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

Abstract: A new algorithm for finding the critical paths is proposed by using coding graph and without topological sort. By extending the data structure of the adjacency lists in the graph, the graph is stored in the same storage space with the algorithm. Beginning from the source node of the graph, by using the rule of getting the maximum number in the weighing calculation and breadth-first search, it encodes all nodes in the graph recursively. That recursively accessing the adjacent node and starting from the current node is the process of re-estimation about preceding node set and the length value from the adjacent node to the source node. After creating the coding graph, by inversing search, it can find all critical paths and the length from destination node to source node. Compared with the traditional algorithms, the algorithm proposed is simpler, more understandable and needs less storage space. The time complexity is O(n+e), which is lower than O(n2) of the traditional algorithm.

Key words: coding graph, critical paths, Activity on Edge(AOE) network, breadth-first search, time complexity

中图分类号: 

• TP311.4