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

Question

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

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

天真地认为它一定是可能的，因为在图中深处会有很多节点，它们的同义词就在它们上方一点点，并且不受图顶部变化的影响。

顺便说一句:支配树的主题被编译器人员“拥有”并且在经典图论书籍中没有提及它是很奇怪的。我使用它的应用程序——我的 FindRoots java 堆分析器——与编译器理论无关。

澄清:我在这里谈论的是有向图。我说的“根”其实就是可达性最大的节点。我已经更新了上面的文本，将对“树”的引用替换为“图形”。我倾向于将它们视为树，因为形状主要是树状的。该图实际上是 Java 堆中的对象，正如您可以想象的那样，它具有合理的层次结构。我发现在进行 OOM 泄漏分析时支配树很有用，因为您感兴趣的是“是什么让这个对象保持事件状态？”答案最终是它的支配者。支配树让你<咳咳>看到木头而不是树木。但有时很多垃圾会漂浮到树顶，所以你的树根下面有成千上万的 child 。对于这种情况，我想尝试计算以根的每个直接子节点(在原始图中)为根的支配树，然后可能向下一个级别等等。 (我暂时不想担心反向链接的可能性:)

Answer 1

boost::lengauer_tarjan_dominator_tree_without_dfs可能有帮助。