﻿基于广度优先遍历的关键路线生成树算法<br>A Critical Path Spanning Tree Algorithm Based on Breadth-First Traversal

# 设为首页加入收藏

Computer Science and Application
Vol.2 No.2(2012), Article ID:731,5 pages DOI:10.4236/CSA.2012.22010

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

Dongmei Fu1, Dingfu Lian2

School of Automation, University of Science and Technology, Beijing

Email: liandingfu@126.com

Received: Apr. 21st, 2012; revised: May 14th, 2012; accepted: May 25th, 2012

ABSTRACT：

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 simulation 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.

Keywords: Project Management Graph Model; Spanning Tree; Critical Path; Breadth-First Traversal

Email: liandingfu@126.com

1. 引言

2. 图的相关理论

2.1. 有向图的概念和表示

2.2. 图的广度优先遍历

(a)(b)(c)

Figure 1. Two representation of digraph. (a) Digraph G; (b) Son adjacency list of G; (c) Father adjacency list of G

Figure 2. Breadth-first traversal of graph

2.3. 项目管理图模型的定义

(1) 存在一个所有节点的根节点，不具有实际意义，仅表示项目的开始，该节点没有父节点；

(2) 根节点外的每个节点表示项目的一道工序或一个任务，节点属性可以包括项目某道工序或任务的编号、名称、工期等信息；

(3) 节点之间的箭线表示工作之间的逻辑关系；

(4) 根节点到除根节点以外的任意一个节点都至少存在一条路线；

(5) 图中不存在环。

3. 一种新的广度优先关键路线生成算法

3.1. 回溯最大路线算法

Figure 3. The flow chart of the backtracking maximum path algorithm

3.2. 广度优先最大路线生成算法

Figure 4. The flow chart of the maximum path spanning tree algorithm

3.3. 算法的优化

4. 结果仿真

Figure 5. Example of project management graph model

Figure 6. Result of critical path spanning tree algorithm

Table 1. Maximum path of the graph model in Figure 3

5. 结论

[1]       乞建勋, 李星梅, 王强. 等效子网络构建的理论与方法[J]. 管理科学学报, 2010, 13(1): 40-43.

[2]       李宁, 吴之明. 网络计划技术的新发展——项目关键链管理(CCPM) [J]. Highway, 2002, 10: 83-86.

[3]       刘芳, 王玲. 基于动态规划思想求解关键路径的算法[J]. 计算机应用, 2006, 26(6): 1440-1442.

[4]       徐志勇, 张开富, 李正兰, 姜寿山. 一种面向航空产品的分级网络计划方法[J]. 计算机集成制造系统, 2006, 12(5): 24-28.

[5]       刘秀凤. 网络计划技术优化方法在建筑工程施工管理中的应用研究[D]. 天津大学, 2008: 45-50.

[6]       师海忠. 有向图语言[J]. 计算机工程与应用, 2011, 22: 53-56.

[7]       T. H. Cormen, C. E. Leiserson, R. L. Rivest, et al. Introduction to algorithms [M]. 北京: 机械工业出版社, 2006.

[8]       D. West. Introduction to graph theory [M]. 北京: 机械工业出版社, 2006.

[9]    J. 邦詹森 [丹], G. 古廷 [英]. 有向图的理论、算法及其应用[M]. 北京: 科学出版社, 2007: 155-158.

[10]    褚春超，郑丕谔, 邬旺. 单代号网络图的计算机辅助生成研究[J]. 计算机辅助设计与图形学学报, 2005, 17(9): 2133-2137.

[11]    R. E. Tarjan. Data structures and network algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 1983: 234-238.

[12]    S. Even. Graph algorithms. New York: Computer Science Press, 1979: 23-28.

[13]    A. Datta. Efficient graph algorithms on a linear array with a reconfigurable pipelined bus system. 15th International Proceedings of Parallel and Distributed Processing Symposium, 2001: 234-238.

[14]    V. Kumar, E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. Parallel and Distributed Processing, 1996: 132-135.

NOTES

*基金项目：北京市教育委员会重点学科共建项目资助(xk10008 0537)。