一种将有向无环图转换成代数表达式树的方法  

Method for Transforming Directed Acyclic Graph into Algebraic Expression Tree

作　　者：李红豫[1] 王郁昕[1] LI Hong-yu;WANG Yu-xin(Beijing Union University,Beijing 100101,China)

机构地区：[1]北京联合大学,北京100101

出　　处：《计算机科学》2020年第S02期584-590,共7页Computer Science

基　　金：北京市教育委员会科研计划项目(KZ201911417048)。

摘　　要：文中给出一种将有向无环图转换成代数表达式树的方法,该方法能够实现图的串联合并、并联合并和串行化合并,并且能够处理图中的函数型顶点。与以往的转换方法相比,文中所给出的转换能够处理类型更为广泛的图和顶点,因此应用也更为广泛。在给出转换方法的同时对转换的运行时间也进行了分析,考虑到实际应用情况,转换时间只与图中边的数量有关,所以转换的效率较高。This paper presents a method for transforming a directed acyclic graph into an algebraic expression tree.This method can achieve series merging,parallel merging,and serialization merging of graphs,and it can handle functional vertices in graphs.Compared with the previous transformation methods,the transformation given in this paper can deal with moretypes of graphs and vertices,so it is more widely used.This article gives the conversion method and analyzes the running time of the conversion.Considering the actual application situation,the conversion time is only related to the number of edges in agraph,so the conversion time efficiency is high.

关 键 词：算法 有向无环图 树 顶点 合并 梯形图 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]