木の直径
Abstract
深さ優先探索 を2回やれば木$ T = (V, E)の直径が求まる (Double sweep method). $ O(|V|)time. Explanation
木の直径は, 以下のアルゴリズムで求まる.
Algorithm (Double sweep method)
Input:
木$ T = (V, E).
Output:
木$ Tの直径$ \mathop{\mathrm{diam}}(T).
1. 木$ T = (V, E)の任意の頂点$ v_0 \in VからDFSを行い, $ vから各頂点への距離を求める.
2.$ vからの距離が最も遠かった点$ uからDFSを行う.
3. 頂点$ vからの距離が最大の点を$ vとし, $ u, v間の距離$ dを出力する.
なお, この方法では一般のグラフの直径は求まらないことに注意.
Implementation
Input
グラフ (頂点は0-indexed) の隣接リスト T
辺重み行列 w (w[u][v] が辺$ uvの重みを表す.)
Output
木$ Tの直径を与える頂点対$ (u, v)
木$ Tの直径$ d
Time complexity
$ O(|V|)time.
code:python
def tree_diameter(T, w):
def dfs(r):
depth = -1 * N # the depth of each vertex d = 0 # current depth
while stack:
v, p, st = stack.pop()
if st == 0: # visited v for the first time
d += (0 if p == -1 else wpv) n_children = 0
if n_children == 0:
n_children += 1
else:
n_children += 1
if n_children == 0: # v is a leaf
d -= (0 if p == -1 else wpv) elif st == 1: # now searching
continue
else: # search finished
d -= (0 if p == -1 else wpv) return depth
N = len(T); v0 = 0
dist = dfs(v0)
u, _ = max(enumerate(dist), key=lambda x: x1) dist = dfs(u)
v, d = max(enumerate(dist), key=lambda x: x1) return (u, v), d
Verification
References