递归计算支配树的有效方法？

我正在使用具有路径压缩的Lengauer和Tarjan算法来计算有数百万个节点的图的支配树.算法非常复杂,我不得不承认我没有花时间完全理解它,我只是使用它.现在我需要计算根节点的直接子节点的支配树,并可能将图形向下递减到重复此操作的某个深度.即,当我为根节点的子节点计算支配树时,我想假装根节点已从图中移除.

我的问题是,是否有一个有效的解决方案,利用已经在根节点的初始支配树中计算的直接支配者信息？换句话说,我不想从头开始为每个孩子,因为整个过程非常耗时.

天真地看起来一定是可能的,因为在图表的内部会有很多节点,这些节点在它们之上只有一点点,并且不受图形顶部变化的影响.

顺便说一句:在统治者树的主题是由编译人员"拥有"并且在经典图论的书中没有提到它,这是奇怪的.我正在使用它的应用程序 - 我的FindRoots java堆分析器 - 与编译器理论无关.

澄清:我在这里谈论有向图.我所指的"根"实际上是具有最大可达性的节点.我已经更新了上面的文本,用"graph"替换了对"tree"的引用.我倾向于将它们视为树木,因为形状主要是树等.该图实际上是java堆中的对象,您可以想象它是合理的层次结构.我发现主导树在进行OOM泄漏分析时很有用,因为你感兴趣的是"是什么让这个物体保持活力？" 答案最终是它的统治者.支配树允许你看到木头而不是树木.但有时很多垃圾漂浮在树顶,所以你有一个直接在它下面有数千个孩子的根.对于这样的情况,我想尝试计算根植于根的每个直接子节点(在原始图形中)的支配树,然后可以进入下一级别,依此类推.(我试着暂时不担心反向链接的可能性:)

boost::lengauer_tarjan_dominator_tree_without_dfs 可能有帮助.