图在互联网技术中有及其广泛的应用,但随着互联网的迅猛发展,图的规模也变得非常庞大,如何对图进行简化从而提升系统的扩展性是研究界关注的热点问题之一。传递归约是图操作中的核心操作,通过去除有向无环图G中的冗余边来实现简化的目的。简化后的有向无环图与G有相同的传递闭包。但是现有的传递归约算法的时间和空间复杂度较大,无法处理大规模有向无环图。针对现有的问题,本文提出了适用于大图的传递归约算法,具体的研究内容如下。首先,根据冗余边的性质,提出利用已有的可达性查询算法来加速冗余边判断的思路。考虑到计算每个兄弟的可达性的复杂度较高,提出将兄弟顶点按照拓扑排序的结果依次处理的算法来得到传递归约的结果。其次,针对出度大且冗余边很少的顶点可能存在处理代价高的问题,提出了对顶点按照(出度+入度)进行升序排序,依次处理每个顶点的方法来避免随机处理存在的冗余计算问题。该方法对每个被处理顶点都检查双向冗余边,并将确认的冗余边在图的邻接表中进行标记。其好处是先将度小的顶点处理完,后处理度较大的顶点时,和度大顶点关联的好多边都已被标记完成,从而有效减少了度大顶点关联的边的处理数量,降低度大顶点的处理代价。最后,本文基于28个不同大小的真实数据集进行实验,从多个角度通过实验结果对所提出算法的高效性进行对比与分析,验证了该算法的高效性和可扩展性。