直径

2ノード間距離のうち最大のものを，そのグラフの直径という．ここでいう距離は，辺の重みは考慮しない．

木の直径は，2回のDFSで求めることができる．具体的には，任意のノードについて，最も遠いノードを求め，そのノードからまた最も遠いノードを求めると，後者の距離が木の直径である．以下に証明を示す．

証明

任意に選択したノード\(r\)から最も遠いノード\(x\)は直径の端点にならないと仮定する．直径(複数ありうる)の端点の集合を\(\mathbb{E}\)とする．\(r\)->\(x\)パスが直径と最初に交わる点が存在すればそれを\(h\)とする．

1. \(h\)が存在する時

\(r\)->\(h\)->\(x\)となるパスが存在する．この時，\(h\)は直径上にあるので，\(h\)から最も遠いノードは\(\mathbb{E}\)に属するノードである．ここで，\(r\)から最も遠いノードは\(x\)なので\(x\)は\(\mathbb{E}\)に属する．これは\(x\)が直径の端点にならないことに⽭盾する．

2. \(h\)が存在しない時

以下の式から，\(x\)を端点とする直径を構成することができるため，\(x\)が直径の端点にならないことに⽭盾する．

\(dist(r, x) \geq dist(r, h) + max_{u \in \mathbb{E}}(dist(h, u))\)

よって\(dist(h, x) \geq + max_{u \in \mathbb{E}}(dist(h, u))\)

以上から，背理法より，任意に選択したノード\(r\)から最も遠いノード\(x\)は直径の端点になる．したがって，任意のノードについて，最も遠いノードを求め，そのノードのから最も遠いノードまでの距離が直径となる．

コード

pair<int, int> dfs(int node, int parent, vector<vector<int>> &g) {
  pair<int, int> ret = {0, node};
  for (int &e: g[node]) {
    if (e == parent) continue;
    pair<int, int> tmp = dfs(e, node, g);
    tmp.first++;
    chmax(ret, tmp);
  }
  return move(ret);
}

int diameter(vector<vector<int>> &g) {
  pair<int, int> d = dfs(0, -1, g);
  d = dfs(d.second, -1, g);
  return d.first;
}