算法图算法

有向图的必经点,支配树

字数统计: 5.1k字   |   阅读时长: 22分
, ,

摘要: 有向图的必经点，支配树

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个从业务场景中抽象出来的图论的问题：有向图的必经点。给定有向图上的两个点 S 和 T，从 S 走到 T 有若干条路径，如果图上存在某个点 V，从 S 出发不论走哪条路径到 T，都必须经过点 V，那么点 V 就是有向图上从 A 到 B 的必经点。

在流程图、食物链、垃圾回收(内存管理)等实际问题中都可以抽象出这种有向图的必经点的问题，支配树是解决这类问题的数据结构。本文我们先对支配树进行定义，然后以垃圾回收场景为例看一下支配树的应用，之后介绍 DAG 和一般有向图下求支配树的算法，并解决模板题，题解代码可以作为模板使用。算法中涉及到一些数学证明，本文跳过了，感兴趣的可以看后面的论文原文。

$0 背景

问题

给定有向图，起点 S，终点 T。若从 S 到 T 的每条路径都要经过某个点 u，则 u 是有向图从 S 到 T 的必经点：所有 S 到 T 的路径中点的交集。

若从 S 到 T 的每条路径都要经过某条边 $e=uv$，则 e 是有向图从 S 到 T 的必经边(桥)：所有 S 到 T 的路径中边的交集。

这是比较难的问题，因为环上的点可能是必经点也可能不是必经点，所以把 SCC 缩点形成 DAG 这种有向图中常用的办法在这里不能用。

作为对比，无向图的必经点和必经边的问题相对简单：

支配树(Dominated Tree)的定义

对于有向图 D, 起点 S，终点 T，S -> T 可能有很多条路径，在所有 S -> T 的路径中都必经的点，称为支配点。

删了该点，将不再存在 S -> T 的路径，因此称起点为 S 时，该点支配了 T。

S -> T 中可能有很多支配点，由这些支配点构成的树，称为支配树。

支配树的性质：

  • S 为树根
  • 根到树上任一点的路径经过的点均为根支配的点

任意子树也有上述性质：

  • 子树的根到子树内任一点的路径经过的点为该子树的根支配的点

支配树的例子

以下面的有向图为例：

对应的支配树为：

支配树的通俗理解

对于一个流程图(单源点的有向图)，除源点外都有每个点都有唯一的idom（直接支配者），且不成环，故所有的 (idom(w), w) 边形成一棵树，u 支配 v 当且仅当 u 是树中 v 的祖先。

GC 场景支配树的应用

分析内存泄漏问题时，可能用到一种叫支配树视图的工具。如果把对象之间的引用关系看做一张有向图(可以存在环)的话，对象的支配树体现了对象之间的支配关系。

如果所有指向对象B的路径都要经过对象A，则认为对象A支配对象B。如果对象A是离对象B最近的支配对象，则认为对象A是对象B的直接支配者。

在 GC 领域，可以用来求深堆的大小。GC 中深堆和浅堆的定义如下：

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

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

有向图求支配树的算法

有向图上求支配树的算法为 Lengauer-Tarjan 算法，如果是 DAG 的话，算法可以简化。后面分别介绍 DAG 和一般有向图上支配树的算法以及模板题。

对于 DAG: 拓扑排序 + 树上倍增

  • 拓扑排序
  • LCA

对于一般有向图: Lengauer-Tarjan 算法

  • dfs 树
  • dfn 序
  • 带权并查集

$1 DAG 上求支配树

如果是 DAG，可以不用 Lengauer Targan。

算法

  • 原图 D 的基础上建立 RD
  • 将 D 进行拓扑排序，若 D 有多个入度为 0 的结点，可以用超级源
  • 按拓扑序遍历节点，当前为 u:
    • 在 RD 中，u 的祖先的支配点已经建立好
    • 找到 u 在 RD 中的所有父节点 fa，这些父节点的 lca 就是 u 的支配点 idom[u]。

最终得到的 DT 为答案。

模板题 P2597 灾难

问题

用一种叫做食物网的有向图来描述生物之间的关系：

  • 一个食物网有 n 个点，代表 n 种生物，生物从 1 到 n 编号。
  • 如果生物 x 可以吃生物 y，那么从 y 向 x 连一个有向边。
  • 这个图没有环。
  • 图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存。
  • 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
  • 如果某个消费者的所有食物都灭绝了，它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。

分析

建图 D：当前点 -> 以当前点为食的点(一个点的入度越多，它可以选择的食物越多)

原图中存在一些没有入度的点(生产者，不依赖食物)

给定一个DAG，求如果删去一个点，有多少个点会被影响

如果删去某个点，对于任意一个原先有入度的点来说，如果因此没有入度，则该点死去：删去与该点相连的边，重复迭代直至所有点死去。

如果删去一个点后，某个点无法连向原图中无入度的点(超级源)，则它死。

算法

1
2
3
4
建图 D 和 反图 RD
对 D 加超级源，对 RD 加超级汇，并求 D 的 indegrees
带着超级源求原图 D 的拓扑序 vector<int> topo_order;
初始化支配树 vector<vector<int>> DT(n + 1);

DAG 求支配树的过程

(1) 按原图的拓扑序枚举节点 u，找到 u 在 RD 中的所有父节点 fa，这些父节点的 lca 就是 u 的支配点 idom[u]。

1
2
3
4
5
6
7
int k = RD[u].size();
int idom = RD[u][0];
for(int j = 1; j < k; ++j)
{
    int fa = RD[u][j];
    idom = lca(idom, fa, d, f);
}

(2) DT 中连接一条边 idom -> u

1
DT[idom].push_back(u);

(3) DT 中 u 的祖先链在 f[u][k] 中要更新

1
2
3
4
5
6
7
8
f[u][0] = idom;
d[u] = d[idom] + 1;
int p = 1; // step = 2 ^ p
while(p <= m && f[f[u][p - 1]][p - 1] != -1)
{
    f[u][p] = f[f[u][p - 1]][p - 1];
    ++p;
}

(1) 中有一步 lca 的过程，这一步就是树上倍增求 LCA 的模板，参考 LCA,树上倍增,树上差分

求出支配树 DT 后，对 DT 做 dfs 求各个节点的 size，size - 1 为当前节点的答案。

代码 (模板、C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int lowbit(int n)
{
    return n & (-n);
}

int highbit(int n)
{
    int p = lowbit(n);
    while(p != n)
    {
        n -= p;
        p = lowbit(n);
    }
    return p;
}

int lca(int x, int y, const vector<int>& d, const vector<vector<int>>& f)
{
    // d[x] >= d[y]
    if(d[x] < d[y])
        return lca(y, x, d, f);
    // 将 y 向上调整直到和 x 一个深度
    int delta = d[x] - d[y];
    while(delta > 0)
    {
        x = f[x][log2(highbit(delta))];
        delta -= highbit(delta);
    }
    if(x == y)
        return x;
    int n = d.size();
    int m = log2(n);
    while(true)
    {
        if(f[x][0] == f[y][0])
            break;
        int k = 1;
        while(k <= m)
        {
            if(f[x][k] == -1 || f[y][k] == -1)
                break;
            if(f[x][k] == f[y][k])
                break;
            ++k;
        }
        x = f[x][k - 1];
        y = f[y][k - 1];
    }
    return f[x][0];
}

int dfs(const vector<vector<int>>& DT, int u, vector<int>& result)
{
    int size = 1;
    for(int v: DT[u])
        size += dfs(DT, v, result);
    result[u] = size - 1;
    return size;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> D(n + 1);
    vector<vector<int>> RD(n + 1);
    // 建图
    for(int i = 1; i <= n; ++i)
    {
        int v;
        while(cin >> v && v > 0)
        {
            D[v].push_back(i);
            RD[i].push_back(v);
        }
    }
    // 超级源 : 0
    vector<int> indegree(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        if(RD[i].empty())
        {
            RD[i].push_back(0);
            D[0].push_back(i);
        }
        indegree[i] = RD[i].size();
    }
    // 拓扑排序
    vector<int> topo_order;
    queue<int> q;
    q.push(0); // 超级源
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        for(int v: D[u])
        {
            --indegree[v];
            if(indegree[v] == 0)
                q.push(v);
        }
    }
    vector<vector<int>> DT(n + 1);
    // 2 ^ m <= n
    // log2(2^m) <= log2(n)
    // m <= log2(n)
    int m = log2(n);
    vector<vector<int>> f(n + 1, vector<int>(m + 1, -1));
    // f[u][k] := u 的第 2^k 个祖先
    vector<int> d(n + 1, -1);
    // d[u] := u 在 DT 中的深度，超级源为 0
    d[0] = 0;
    for(int u: topo_order)
    {
        if(RD[u].empty()) // DT 的树根是超级源
            continue;
        int k = RD[u].size();
        int idom = RD[u][0];
        for(int j = 1; j < k; ++j)
        {
            int fa = RD[u][j];
            idom = lca(idom, fa, d, f);
        }
        DT[idom].push_back(u);
        // DT 中连接一条边 idom -> u
        // u 的祖先链在 f 中要更新
        f[u][0] = idom;
        d[u] = d[idom] + 1;
        int p = 1; // step = 2 ^ p
        while(p <= m && f[f[u][p - 1]][p - 1] != -1)
        {
            f[u][p] = f[f[u][p - 1]][p - 1];
            ++p;
        }
    }
    vector<int> result(n + 1);
    // result[i] := DT 中 i 的 size - 1
    dfs(DT, 0, result);
    for(int u = 1; u <= n; ++u)
        cout << result[u] << endl;
}

$2 一般有向图上求支配树

算法推导

1
2
3
dfn[u] := u 的 dfn 序
sdom[u] := x 的半支配点
idom[u] := x 的最近支配点

半支配点

定义

对于 u，存在 v，可以通过一些点 $v_{i}$ (不含 u, v)，到达 u ($v \rightarrow v_{i} \rightarrow u$)，且 $\forall i$, $dfn[v_{i}] > dfn[u]$，对于所有满足条件的 v，dfn[v] 最小的 v 称为半支配点，记 sdom[u] = v

性质

  1. 半支配点唯一(支配点可以有多个)
  2. 对任意 u，其半支配点必为其在 dfs 树上的祖先
  3. 对任意 u ($u \neq S$)，其支配点必为 u 的半支配点的祖先节点
  4. 若 u 为 v 的祖先，则 idom[v] 是 u 的后代或者是 idom[u] 的祖先

sdom[u] 到 u 的路径，相当于 dfs 树外有一条路，并且 sdom[u] 为离根最近的那个点。

求法

依赖定理及其证明，有点难，下面直接记录结论，证明参考前面的两个链接。

对于 u，枚举 $(v, u) \in E$ (反图)

  • dfn[u] > dfn[v] : sdom[u] = min(v)
  • dfn[u] < dfn[v] : sdom = min(sdom[k]), k 为 dfn[k] > dfn[u] 且 dfs 树中 k 能到 v

按照 dfn 序从大到小枚举 u，则考查 u 时，sdom[k] 已经有了

第二种情况，怎样高效找到 k，sdom[k] 的最小值, u 的祖先链上 sdom 的最小值，用并查集。

最近支配点

定义

若图中存在 u, v，且 v 支配 u，且 u 的其它支配点均支配 v

则 v 是 u 的最近支配点，记为 idom[u] = v

性质及求法

依赖定理及其证明，有点难，下面直接记录结论，证明参考前面的两个链接。

对于 u(非源点)，k 为满足以下条件的点 v 中 sdom[v] 最小的一个

  • dfs 树中存在以下路径：sdom[u] -> v -> u
  • 等价条件：
    • dfn[v] > dfn[u]
    • v 在 u 的子树中, 即 v 沿着父亲链能到 u
1
2
idom[u] = sdom[u]  (sdom[u] = sdom[k])
idom[u] = idom[k]  (sdom[k] < sdom[u])

高效求 sdom[u]

参考之前【半支配点-求法】

对于任意 u(非源点r)：

算法 (Lengauer Tarjan)

算法流程

  1. 初始化、跑一遍 DFS 得到 DFS 树和标号
  2. 按 dfn 序从大到小利用【高效求 sdom[u]】求出 sdom
  3. 按照【最近支配点-性质及求法】求出所有能确定的 idom，剩下的点记录下和哪个点的 idom 是相同的
  4. 按照 dfn 序从小到大再跑一次，得到所有点的 idom

实现

要维护的数据：

1
2
3
4
5
6
7
dfn_id(dfnid): dfn 序为 dfnid 的点
id_dfn(u): 节点 u 的 dfn 序
fa[u]: u 在 dfs 树上的父节点
sdom[u]: u 的 sdom 的 dfs 序, 初始化为 u
idom[u]: u 的 idom 节点
RD[u]: 有边直接连接到 u 的点集
sdom_set[u]: sdom 对应的节点为 u 的点集

算法流程中的第 2,3 步可以一起做。

通过一个数据结构维护一个森林，支持加入一条 dfs 树的边 add(u, v) 和查询点 u 到根的路径上的点 v 的 sdom 的最小值对应的节点，记为 k， k = query(u)。

求 u 的 sdom 只需要对它的所有直接前驱 query 一次，对每个前驱 v：k = query(v) sdom 取最小值时的节点 k, sdom[k] 为该前驱提供的候选。

参照【高效求 sdom[u]】中的流程:

  • 第一类点编号比它小，它们还没有处理过，所以自己就是根，query(v) 就能取得它们的值
  • 对于第二类点，query(v) 查询的就是满足 dfs 树中 v 在 k 的子树中的 k 的 sdom[k] 的最小值对应的节点。和【高效求 sdom[u]】中是一致的。

然后把该点 u 加入它的 sdom 节点对应的 set 里，在 dfs 树中连上 u 与父节点 fa[u] 的边。
现在 u 的父节点到 u 的这棵子树中已经处理完了，所以可以对父亲的 set 里的每个点求一次 idom 并且清空 set。

对于 set 里的每个点 v，求出 query(v)，此时 dfs 树中 fa[u] -> query(v) -> v，于是直接按照【最近支配点-性质及求法】:

  • 如果 sdom[query(v)] == sdom[v]，则 idom[v] = sdom[v] = fa[u]
  • 否则可以记下 idom[v] = idom[query[v]]，实现时可以暂时先写 idom[v] = query[v]，留到第 4 步处理。

最后从小到大扫一遍完成第4步，对于每个 u:

  • idom[u] == sdom[u] 的话，就已经是第3步求出的正确的 idom 了
  • 否则这是第 3 步留下的待处理点，令 idom[u] = idom[idom[u]] 即可。

对于这个数据结构，可以选择并查集。不过因为需要查询到根路径上的信息，所以不方便写按秩合并，但是仍然可以路径压缩，压缩时保留路径上的最值就可以了，只有路径压缩的并查集的复杂度是 $O(logN)$。

原论文还提到了一个实现方法，能够把这个并查集优化到 $\alpha$ 的复杂度，即原文《A Fast Algorithm for Finding Dominators in a Flowgraph》里面的参考文献 14 — Tarjan 的另一篇文章《Applications of Path Compression on Balanced Trees》。

例子

原图与对应的 dfs 树，dfn 序

模板题： P5180 【模板】支配树

问题

给定一张有向图，求从 1 号点出发，每个点能支配的点的个数（包括自己）

1
2
n <= 2e5
m <= 3e5

代码 (模板、C++)

代码注释中说明了维护的变量的含义，与前面的算法中对照。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFindSet
{
public:
    UnionFindSet(int N)
    {
        _father = vector<int>(N + 1);
        weight = vector<int>(N + 1);
        for(int i = 1; i <= N; ++i)
        {
            _father[i] = i;
            weight[i] = i;
        }
    }

    int query(int u, const vector<int>& sdom)
    {
        // 返回 u -> 根的路径上的节点 v 中 sdom 最小值对应的节点
        _find(u, sdom);
        return weight[u];
    }

    void add(int u, int v)
    {
        // 加边 u -> v(fa[u])
        _father[u] = v;
    }

private:
    vector<int> _father, weight;

    int _find(int u, const vector<int>& sdom)
    {
        // 返回根，用于路径压缩
        if(_father[u] == u)
            return u;
        int root = _find(_father[u], sdom);
        // 路径压缩 _father[u] = root 之前做以下比较和更新
        if(sdom[weight[_father[u]]] < sdom[weight[u]])
            weight[u] = weight[_father[u]];
        return _father[u] = root;
    }
};


void dfs(const vector<vector<int>>& D, int u, int& dfnid, vector<int>& id_dfn, vector<int>& dfn_id, vector<int>& fa, vector<int>& sdom)
{
    id_dfn[u] = ++dfnid;
    dfn_id[dfnid] = u;
    sdom[u] = id_dfn[u];
    for(int v: D[u])
        if(!id_dfn[v]) // v 已经访问过
        {
            dfs(D, v, dfnid, id_dfn, dfn_id, fa, sdom);
            fa[v] = u;
        }
}

int dfs2(const vector<vector<int>>& DT, int u, vector<int>& cnts)
{
    int ans = 1;
    for(int v: DT[u])
    {
        if(u != v)
            ans += dfs2(DT, v, cnts);
    }
    return cnts[u] = ans;
}

vector<vector<int>> dominated_tree(const vector<vector<int>>& D, const vector<vector<int>>& RD, const int S, const int N)
{

    int dfnid = 0;
    // dfn_id[dfnid] := dfn 序为 dfnid 的节点
    // id_dfn[u] = 节点 u 的 dfn 序;
    // fa[u] := dfs 树中 u 的父节点
    vector<int> id_dfn(N + 1), dfn_id(N + 1), fa(N + 1);
    // sdom[u] := u 的 sdom 的 dfn 序
    // idom[u] := u 的 idom 的节点编号
    vector<int> idom(N + 1), sdom(N + 1);

    // 预处理 dfn_id, id_dfn, fa, sdom
    dfs(D, S, dfnid, id_dfn, dfn_id, fa, sdom);

    UnionFindSet forest(N);
    vector<vector<int>> sdom_set(N + 1);
    // sdom_set[u] := sdom 为 id_dfn[u] 的点集
    // 求 sdom[u], 顺便求 sdom_set[fa[u]] 中的 v 的 idom[v]
    for(int dfn = dfnid; dfn >= 2; --dfn)
    {
        int u = dfn_id[dfn];
        // 求 u 的 sdom 只需要对它的所有直接前驱 query 一次
        // 求得前驱中的 sdom 最小值即可
        for(int v : RD[u])
        {
            // id_dfn[u] > id_dfn[v] 时
            //   v 尚未访问到，所以它自己就是根, query 的结果就是它自己
            // id_dfn[u] < id_dfn[v] 时
            //   sdom[u] = min(sdom[k]) 其中 dfn[k] > dfn[u] 且 k 能到 u
            //     即 u -> v -> ... 的祖先链中 sdom 的最小值
            //   query(v) 求的正是 u -> v -> ... dfs 树上已经连边的 v 的根节点
            //     这条链上的 sdom 最小值对应的节点
            if(id_dfn[v])
            {
                sdom[u] = min(sdom[u], sdom[forest.query(v, sdom)]);
            }
        }
        sdom_set[dfn_id[sdom[u]]].push_back(u);
        int fp = fa[u];
        // 给森林加一条 dfs 树上的边
        forest.add(u, fa[u]);
        // 现在 fa[u] -> u 的这棵子树中已经处理完了
        // sdom 为 id_dfn[fa[u]] 的节点 v 可以处理了
        for(int v : sdom_set[fp])
        {
            int k = forest.query(v, sdom);
            // 此时 dfs 树中 fa[u] -> k -> v
            if(sdom[k] == sdom[v])
            {
                // sdom[v] 也就是 fa[u] 的 dfn 序
                idom[v] = fp;
            }
            else
            {
                // 按公式是 idom[v] = idom[k]
                // 先记下 idom[v] = k，之后集中处理
                idom[v] = k;
            }
        }
        sdom_set[fp].clear();
    }
    // 之后集中处理 idom[v] = idom[k] 的这些点
    for(int dfn = 2; dfn <= dfnid; ++dfn)
    {
        int u = dfn_id[dfn];
        if(idom[u] == dfn_id[sdom[u]])
            idom[u] = idom[u];
        else
            idom[u] = idom[idom[u]];
    }
    // 由 idom[u] 建 DT
    vector<vector<int>> DT(N + 1);
    for(int u = 1; u <= N; ++u)
        DT[idom[u]].push_back(u);
    return DT;
}

int main()
{
    int n, m;
    cin >> n >> m;
    // 建图
    vector<vector<int>> D(n + 1), RD(n + 1);
    for(int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        D[u].push_back(v);
        RD[v].push_back(u);
    }
    // 源点，这里给了源点，不用设超级源
    int S = 1;

    // 给定图 D，反图 RD，源点 S，求支配树
    vector<vector<int>> DT = dominated_tree(D, RD, S, n);

    vector<int> cnts(n + 1);
    dfs2(DT, S, cnts);

    for(int u = 1; u <= n; ++u)
        cout << cnts[u] << " ";
    cout << endl;
}

$4 论文原文

《A Fast Algorithm for Finding Dominators in a Flowgraph》

Share