支配树（Dominator Tree）

MAT中的支配树

在使用MAT分析项目的内存泄漏问题时，其中有一个支配树（Dominator）视图。如果我们把Java对象之间的引用关系看做一张有向图（可以存在环）的话，对象的支配树体现了对象之间的支配关系。如果所有指向对象B的路径都要经过对象A，则认为对象A支配对象B。如果对象A是离对象B最近的支配对象，则认为对象A是对象B的直接支配者。

支配树定理

除起始节点外都有每个点都有唯一的idom（直接支配者），且不成环，故所有的 (idom(w),w) 边形成一棵树，v支配w当且仅当v是树中w的祖先，这棵树叫做支配树。

对象的支配树有以下性质：

1. 对象A的子树（所有被对象A支配的对象集合）表示对象A的保留集（retained set），即深堆
2. 如果对象A支配对象B，那么对象A的直接支配者也支配对象B
3. 支配树的边与对象引用图的边不直接对应

对象支配树的作用

可以用来求深堆的大小。这里解释一下浅堆和深堆：

• 浅堆表示一个对象结构所占用的内存大小
• 深堆表示一个对象被GC回收后，可真实释放的内存大小

从支配树的性质可以看出，如果释放对象A，则对象A对应的支配树上的子树都将被释放，因为子树上的对象都不可达了，应该被GC回收。所以支配树上某个对象节点的子树上所有对象的大小就是该对象的深堆大小。

支配树的求解方法

简单求解方法

使用 “迭代+DFS”方法实现。时间复杂度是O(mn)。

1. 每次删掉一个点，判断哪些点无法从起始节点r到达
2. 删掉点u后发现点v无法到达，那么点u就是r->v的必经点（点u就是v的支配点）

Lengauer-Tarjan算法

Lengauer-Tarjan算法可以在更优的时间复杂度下求解有向图的支配树。