基于DAG的拓扑排序改进算法及在BOM中的运用  

A New Kind of Algorithm Containing the Topological Sort Based on DAG and its Application To BOM

作　　者：石为人[1] 马振红[1] 张星林 荫华 

机构地区：[1]重庆大学自动化学院,重庆400044

出　　处：《计算机工程与应用》2005年第28期192-194,214,共4页Computer Engineering and Applications

摘　　要：文章讨论了传统的BOM防止嵌套错误算法和低层码计算的算法的实现过程。在分析算法的实现过程后对其原理进行评价的基础上,将BOM树结构和DAG图性质进行比较后对这两种算法进行改进,提出了一种蕴涵了拓扑排序思想的算法。最后编程实现了此算法的伪代码,该算法在实际运用中取得了明显的效果,减少了数据库系统资源的占用,大大提高了数据库的性能和响应能力。Based on the analysis of traditional BOM algorithms of nesting error tolerance and Low-Level Code（LLC） computing,after the comparison of BOM tree structure with Directed Acycline Graph（DAG）,a new kind of algorithms containing the topological sort is proposed and its pseudocode is also implemented in details.The results of its application that could decrease the occupancy of system resources and improve the response speed and performance of database,and show that these algorithms are feasible and effective.

关 键 词：BOM 有向无环图 低层码 AOV-网 拓扑排序 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]