基于广度优先遍历的关键路线生成树算法

A Critical Path Spanning Tree Algorithm Based on Breadth-First Traversal

关键路线的确定对于运用关键路线法进行项目管理具有十分重要的意义。本文首先定义了项目管理图模型,然后在此基础上提出了一种基于广度优先遍历的关键路线生成树算法,最后通过对项目管理图模型的研究,实现了对算法的优化。仿真结果表明,该算法能够生成一棵保留根节点到任意节点最大路径信息的树,通过生成的树能够方便地确定关键路线。

To get critical path is of great significance for the use of critical path method in project management. This paper first defines project management graph model, and then puts forward a critical path spanning tree algorithm based on breadth-first traversal, and then achieves the optimization algorithm through the research of the model. The simula- tion shows that the algorithm can create a tree which keeps the maximum path from the root node to any node in the graph model, and get the critical path easily through the tree.