木
投稿者：CarpDay.icon
木の基本：https://algo-method.com/descriptions/150
1. 木の直径
参考：https://algo-logic.info/tree-diameter/
(1) 定義
木に存在する2つのノードの距離の最大値．最も離れている2点間の距離
「距離＝パス上の枝の本数」でも，枝に長さがあって「距離＝パス上の枝の距離の合計」でもOK
(2) アルゴリズム
任意の点$ s を選ぶ
点$ s から BFS/DFS によって、最も遠くにある点$ u を探索する
点$ u から BFS/DFS によって、最も遠くにある点 $ v を探索する
点$ uから点$ vまでの距離が直径
計算量$ O(N)
(3) コード例
code: python
from collections import defaultdict
from collections import deque
def tree_distance(n: int, adj: defaultdict, r: int) -> tuple:
d = 0 * (n + 1) # rからの距離．1-index
checked = False * (n + 1) # チェック済み判定．1-index
q = deque(r) # これから探索する点を格納するキュー
dr = 0
checkedr = True
max_d, max_v = 0, r # rからの最大距離．最大距離の点
while q:
v = q.popleft()
for u, c in adjv: # 隣接点，(v, u)の距離
if not checkedu:
du = dv + c
if du > max_d:
max_d, max_v = du, u
checkedu = True
q.append(u)
return max_v, max_d, d # rから最も遠い点，rから最も遠い距離，距離（リスト）
def tree_diameter(n: int, adj: defaultdict):
max_v1, max_d1, d1 = tree_distance(N, adj, 1)
max_v2, max_d2, d2 = tree_distance(N, adj, max_v1)
return max_d2
N = 4
ABC = (1,2,2), (1,3,3), (1,4,4) # (端点1，端点2，距離）．木なので枝数は N-1
adj = defaultdict(list)
for a, b, c in ABC:
adja.append((b, c)) # (隣接点，距離）
adjb.append((a, c))
print(tree_diameter(N, adj)) # 直径は 点3,1,4を通る 7
Verified: ABC361E (https://atcoder.jp/contests/abc361/tasks/abc361_e)
2. 木の半径
(1) 定義
他のノードまでの距離の最大値の最小値
直径が偶数のとき，半径＝直径／2．直径が奇数のとき，半径＝(直径+1)／2
「距離＝パス上の枝の本数」でも，枝に長さがあって「距離＝パス上の枝の距離の合計」でもOK
3. 木の中心
参考：https://37zigen.com/diameter-center-tree/
(1) 定義
最も遠い他の点への距離が半径と一致する点．複数存在する場合もある．
「距離＝パス上の枝の本数」でも，枝に長さがあって「距離＝パス上の枝の距離の合計」でもOK
(2) アルゴリズム
任意の点$ s を選ぶ
点$ s から BFS/DFS によって、各点$ uからその子孫までの距離の最大値$ d_uを計算する
$ v \leftarrow sとして，以下のループ開始
$ d_v = 半径なら，点$ vが中心．ループを抜ける．
点 $ vの子のうち，$ d_uが最大となる点を$ uとする．$ v \leftarrow u
計算量$ O(N)
(3) コード例
TBA
4. 木の重心
参考：https://qiita.com/drken/items/4b4c3f1824339b090202
(1) 定義
木に存在する点（とその点に隣接している枝）を削除したとき，作成されるすべての部分木の点数が，元の点数の半分以下となる点
(2) アルゴリズム
木の中心のアルゴリズムと考え方は同じ
ある点$ s から BFS/DFS によって、各点$ u，およびその子孫に存在する点数$ n_uを計算する
$ v \leftarrow sとして，以下のループ開始
$ n_v <= 木の点数/2なら，点$ vが中心．ループを抜ける．
点 $ vの子のうち，$ n_uが最大となる点を$ uとする．$ v \leftarrow u
計算量$ O(N)
(3) コード例
TBA
#木 #グラフ理論 #BFS/DFS