動機

紀錄

Tree

直徑

定義: 相離最遠的兩個點的距離

  1. 走兩次DFS，一次到從這個點最遠，第二次是從最邊邊到最遠
dep = defaultdict(int)
far = None
def dfs(root, fa):
  if root:
    for child in [child for child in root.children if child is not fa]:
      dep[child] = dep[fa]+1
      far = max([far, child], key=lambda x: dep[x])
      dfs(child, root)
dfs(root, None)
dep[far] = 0
dfs(far, None)
print(dep[far])
  1. 走DFS, 紀錄每個點最高與次高的高度，兩者相加就是直徑的候選
diameter = 0
def dfs(root, fa):
  h1, h2 = 0, 0
  if root:
    for child in [child for child in root.children if child is not fa]:
      h = dfs(child, root)+1
      if h > h1:
        h1, h2 = h, h1
      elif h > h2:
        h2 = h
  diameter = max(diameter, h1+h2)
  return h1

重心

重心: 對於樹上的每一個點，計算其所有子樹中最大的子樹節點數，這個值最小的點

  • 子樹都是指無根樹的子樹，即包括“向上”的那棵子樹，並且不包括整棵樹自身。
    • 特性:
      • 最多兩個點
      • 以此點為根，每顆tree的高度不大於N/2
childs = defaultdict(int) # 所有child的子樹的size總和
weight = defaultdict(int) # 子樹中最多Node的子樹的size
centroids = []

# 假設知道Node總數是N
def dfs(root, fa):
  if root:
    for child in [child for child in root.children if child is not fa]:
      dfs(child, root)
      childs[root] += childs[child]
      weight[root] = max(weight[root], childs[child])
    weight[root] = max(weight[root], N-weight[root])
    if weight[root] <= N//2:
      centroids.append(root)

樹分治 (Centroid Decomposition)

讓圖的每個點都有一個parent，但parent都是用當前的重心

fas = defaultdict(lambda x: None)
sizes = defaultdict(int)

def decompose(root, fa):
  size = getSize(root, None)
  centroid = getCentroid(root, None, size)
  fas[centroid] = fa

  for child in centroid.children:
    centroid.children.remove(child)
    child.children.remove(centroid)
    decompose(child, centroid)

def getSize(root, fa):
  sizes[root] = 0
  if root:
    sizes[root] += 1
    for child in [child for child in root.children if child is not fa]:
      sizes[root] += getSize(child, root)
  return sizes[root]

def getCentroid(root, fa, size):
  if not root:
    return None
  else:
    for child in [child for child in root.children if child is not fa]:
      if sizes[child] > size//2:
        return getCentroid(child, root, size)

重鏈分解 (Heavy-light decomposition)

在parent從child中挑一個size最大的child做heavy

fas = defaultdict(lambda x: None)
heavy = defaultdict(lambda x: None)
sizes = defaultdict(int)
def assignHeavy(root):
  sizes[root] = 0
  if root:
    max_wieght = 0
    for child in root.children:
      child_size = assignHeavy(child)
      sizes[root] += child_size
      fas[child] = root
      if max_wieght < child_size:
        max_wieght, heavy[root] = child_size, child
  return sizes[root]

之後就是走訪，先看有沒有heavy，有就先走，並assign到同一條鏈(head) 沒有heavy就開新的鏈

heads = defaultdict(lambda x: None)
def decompose(root, head):
  heads[root] = head
  if heavy[root]:
    decompose(heavy[root], head)
  isNotInHeavy = lambda child: child is not fas[root] and child is not heavy[root]
  for child in [child for child in root.children if isNotInHeavy(child)]:
      decompose(child, child)

Q: 這能幹嘛? A: 這裡

圖

直徑

偏心距: 以最短路徑長度當作距離，找出離此點最遠的一點的距離 直徑: 圖上所有偏心距當中最大的一個

  • 半徑: 圖上所有偏心距當中最小的一個

找所有點的到別的點的最短距離，之後就是找每一點的偏心距，之後就是照定義

// Floyd-Warshall Algorithm
for (int k=0; k<10; ++k)
    for (int i=0; i<10; ++i)
        for (int j=0; j<10; ++j)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

// 計算偏心距
memset(ecc, 0x7f, sizeof(ecc));
for (int i=0; i<10; ++i)
    for (int j=0; j<10; ++j)
        ecc[i] = min(ecc[i], d[i][j]);

// 計算直徑和半徑
int diameter = 0;
int radius = 1e9;
for (int i=0; i<10; ++i)
{
    diameter = max(diameter, ecc[i]);
    radius   = min(radius  , ecc[i]);
}

重心

計算每個點有多少點指到(入度)，之後就是用bfs把入度為0的node放到queue

在bfs中移除node，更新移除後的入度，把入度為0的node放到queue

等結束後，確認剩下最多兩個node

Ref

树的直径 树的重心 演算法筆記 Path A Visual Introduction to Centroid Decomposition Heavy-light decomposition 树链剖分