递归计算主宰树的有效方法?

我使用带有路径压缩的lengauer和tarjan算法来计算一个有数百万个节点的图的主宰树。算法相当复杂,我不得不承认我没有花时间完全理解它,我只是在使用它。现在,我需要计算根节点的直接子节点的主宰树,并可能在图中递归到一定深度,重复这个操作。也就是说,当我为根节点的子节点计算主宰树时,我想假设根节点已经从图中删除。

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

天真地说,这似乎是可能的,因为在图的深处有很多节点的IDOM比它们稍高一点,并且不受图的顶部变化的影响。

顺便说一句:很奇怪,主宰树的主题是由编译人员“拥有”,经典图论书籍中没有提到它。我正在使用的应用程序——我的FixRooJava Java堆分析器——与编译器理论无关。

澄清:我在这里谈论的是有向图。我所指的“根”实际上是具有最大可达性的节点。我已经更新了上面的文本,用“graph”替换了对“tree”的引用。我倾向于把它们当作树,因为形状是 主要地 树状的图形实际上是Java堆中的对象,正如你可以想象的那样,它是合理的层次结构。在进行OOM泄漏分析时,我发现主宰树很有用,因为您感兴趣的是“什么使这个对象保持活动状态?”最终答案是它的主宰者。主宰者树允许您查看木材而不是树木。但是有时候很多垃圾会浮到树的顶部,这样你就有了一个根,在它的正下方有成千上万的孩子。对于这种情况,我想尝试计算根的每个直接子代(在原始图中)的主宰树,然后再向下一级,依此类推。(我暂时不担心有可能出现反向链接:)