Binarization of Minimum Spanning Tree
概要
辺に重みがある \(N\) 頂点からなるグラフ \(G\) の最小全域木 \(T\) を求めた上で、木を頂点に重みがある二分木 \(U\) に変換する。
具体的には、グラフ \(G\) の \(N\) 個の頂点に対応する頂点(番号 \(1, 2, ..., N\))を用意し、グラフ \(G\) 上においてKruskal法で2頂点をマージする順序に合わせて(\(i\) 番目に頂点 \(u_i, v_i\) を重み \(c_i\) の辺でマージするとする)、 頂点 \(u_i, v_i\) をそれぞれ含む2つの二分木を子として持ち、新しい頂点(番号 \(N+i\))を根頂点とする1つの二分木を生成する。(この時、新しい根頂点の重みを \(c_i\) とする)
そして、 \(N-1\) 回のマージによって最終的に1つの二分木 \(U\) を生成する。
この二分木 \(U\) は以下の特徴を持つ
-
\(2N - 1\) 個の頂点からなり、それぞれ \(1, 2, ..., N, N+1, ..., 2N-1\) の番号が付いている
-
頂点 \(2N - 1\) が根頂点となる
-
二分木 \(U\) の頂点 \(v\) (\(1 \le v \le N\)) はMST \(T\) 上の頂点 \(v\) と対応しており、二分木 \(U\) の葉となる。
-
MST \(T\) の任意の頂点ペア \((u, v)\) (\(1 \le u, v \le N\))について、二分木 \(U\) 上の頂点 \(u\) と頂点 \(v\) のLCAとなる頂点の重みは MST \(T\) 上の頂点 \(u, v\) 間のパスに含まれる辺の中の最大の重みになる
この二分木 \(U\) 上で二頂点のLCAを求められるようにすることで、MST上のある二頂点を繋ぐパス上の辺の重みの最大値が \(O(\log N)\) 等で求められる。
計算量
辺数を \(M\) とすると \(O(M \log M)\)
実装
# N: 頂点数
# E = [(c, a, b), ...]: 頂点aと頂点bを重みcの辺が繋ぐ
def binarization_mst(N, E):
L = 2*N-1
# G: 変換後の二分木
G = [[] for i in range(L)]
# W: 変換後の各頂点の重み
W = [0]*L
*p, = range(N)
def root(x):
if x == p[x]:
return x
p[x] = y = root(p[x])
return y
E.sort()
cur = N
*lb, = range(N)
for c, a, b in E:
pa = root(a); pb = root(b)
if pa == pb:
continue
W[cur] = c
G[cur] = [lb[pa], lb[pb]]
if pa < pb:
p[pb] = pa
lb[pa] = cur
else:
p[pa] = pb
lb[pb] = cur
cur += 1
# assert cur == L
return G, W