algorithm-dev

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub today2098/algorithm-dev

:question: Double Sweep(木の直径)
(algorithm/Graph/Tree/double_sweep.hpp)

概要

木の直径を求めるアルゴリズム. ここで木の直径とは,「与えられた木における単純パスの長さの最大値」をいう. また,重みなし無向グラフに対しては,グラフの直径の下界となる.

アルゴリズムの流れは次の通り. ただし,$\operatorname{d}(u,v)$ はノード $u, v$ 間の距離,$\operatorname{ecc}(v)$ は $\max_u \operatorname{d}(v,u)$ を表す(”ecc” は “eccentricity” の略).

  1. 与えられた木上の任意のノード $s$ を選択する.
  2. BFS により,$\operatorname{d}(s,u) = \operatorname{ecc}(s)$ となるノード $u$ を探索する.
  3. BFS により,$\operatorname{d}(u,v) = \operatorname{ecc}(u)$ となるノード $v$ を探索する.
  4. ノード $u$ と $v$ を結ぶ単純パスが,求める木の直径となる.

計算量は,木のノード数を $\lvert V \rvert$ とすると,$\mathcal{O}(\lvert V \rvert)$ となる.

アルゴリズムの説明

アルゴリズムのポイントは,「木上の任意のノードから最も遠くにあるノードは直径の端点になる」ということ. アルゴリズムの正当性を背理法を用いて証明する.

ある木において,「根 $r$ から最も遠いノード $x$ は木の直径の端点にならない」と仮定する. また,木の直径の端点を $u, v$ とおく.

(1) まず,パス $r$-$x$ が直径 $u$-$v$ と交わる場合を考える. この交点となるノードを $h$ とおく. ノード $h$ は直径上にあるため,$h$ から最も離れているノードは $u$ または $v$ となる. しかし,根 $r$ から最も遠いノードは $x$ であり,$x$ は $u$ または $v$ のどちらかになるため,矛盾が生じる.

(2) 次に,パス $r$-$x$ が直径 $u$-$v$ と交わらない場合を考える. 直径上にある点を $h’$ とおく. $\operatorname{d}(r,h’) + \operatorname{d}(h’,x) \geq \operatorname{d}(r,x)$ であることに注意すると,

\[\begin{align} &\operatorname{d}(r,x) \geq \operatorname{d}(r,h') + \max(\operatorname{d}(h',u), \operatorname{d}(h',v)) \notag\\ \Rightarrow &\operatorname{d}(h',x) \geq \max(\operatorname{d}(h',u), \operatorname{d}(h',v)) \notag \end{align}\]

となる.(1) と同様にノード $x$ は $u$ または $v$ のどちらかになるため,矛盾が生じる.

よって,木上の任意のノードから最も遠くにあるノードは直径の端点になることが示された.

参考文献

  1. Clémence Magnien, Matthieu Latapy, and Michel Habib. 2009. Fast computation of empirically tight bounds for the diameter of massive graphs. ACM J. Exp. Algorithmics 13, Article 10 (2009), 9 pages. https://doi.org/10.1145/1412228.1455266.
  2. “直径”. アルゴリズムとデータ構造大全. https://take44444.github.io/Algorithm-Book/graph/tree/diameter/main.html.

問題

Verified with

Code

#ifndef ALGORITHM_DOUBLE_SWEEP_HPP
#define ALGORITHM_DOUBLE_SWEEP_HPP 1

/**
 * @brief Double Sweep(木の直径)
 * @docs docs/Graph/Tree/double_sweep.md
 */

#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

namespace algorithm {

// 木の直径を求める.返り値は直径とその経路.O(|V|).
std::pair<int, std::vector<int> > double_sweep(const std::vector<std::vector<int> > &g, int s = 0) {
    const int vn = g.size();
    assert(0 <= s and s < vn);
    int furthest_node;
    std::vector<int> d(vn);
    std::vector<int> pre(vn);
    std::queue<int> que;
    auto bfs = [&](int s) -> void {
        std::fill(pre.begin(), pre.end(), -1);
        d[s] = 0, pre[s] = -2;
        que.push(s);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            furthest_node = u;
            for(int v : g[u]) {
                assert(0 <= v and v < vn);
                if(pre[v] != -1) continue;
                d[v] = d[u] + 1, pre[v] = u;
                que.push(v);
            }
        }
    };
    bfs(s);
    bfs(furthest_node);
    std::vector<int> path({furthest_node});
    path.reserve(d[furthest_node] + 1);
    for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
    return {d[furthest_node], path};  // pair of (diameter, path).
}

// 重み付き木の直径を求める.返り値は直径とその経路.O(|V|).
template <typename Type>
std::pair<Type, std::vector<int> > double_sweep(const std::vector<std::vector<std::pair<int, Type> > > &g, int s = 0) {
    const int vn = g.size();
    assert(0 <= s and s < vn);
    int furthest_node;
    std::vector<Type> d(vn);
    std::vector<int> pre(vn);
    std::queue<int> que;
    auto bfs = [&](int s) -> void {
        furthest_node = s;
        std::fill(pre.begin(), pre.end(), -1);
        d[s] = 0, pre[s] = -2;
        que.push(s);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            if(d[u] > d[furthest_node]) furthest_node = u;
            for(const auto &[v, cost] : g[u]) {
                assert(0 <= v and v < vn);
                if(pre[v] != -1) continue;
                d[v] = d[u] + cost, pre[v] = u;
                que.push(v);
            }
        }
    };
    bfs(s);
    bfs(furthest_node);
    std::vector<int> path({furthest_node});
    for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
    return {d[furthest_node], path};  // pair of (diameter, path).
}

}  // namespace algorithm

#endif
#line 1 "algorithm/Graph/Tree/double_sweep.hpp"



/**
 * @brief Double Sweep(木の直径)
 * @docs docs/Graph/Tree/double_sweep.md
 */

#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

namespace algorithm {

// 木の直径を求める.返り値は直径とその経路.O(|V|).
std::pair<int, std::vector<int> > double_sweep(const std::vector<std::vector<int> > &g, int s = 0) {
    const int vn = g.size();
    assert(0 <= s and s < vn);
    int furthest_node;
    std::vector<int> d(vn);
    std::vector<int> pre(vn);
    std::queue<int> que;
    auto bfs = [&](int s) -> void {
        std::fill(pre.begin(), pre.end(), -1);
        d[s] = 0, pre[s] = -2;
        que.push(s);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            furthest_node = u;
            for(int v : g[u]) {
                assert(0 <= v and v < vn);
                if(pre[v] != -1) continue;
                d[v] = d[u] + 1, pre[v] = u;
                que.push(v);
            }
        }
    };
    bfs(s);
    bfs(furthest_node);
    std::vector<int> path({furthest_node});
    path.reserve(d[furthest_node] + 1);
    for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
    return {d[furthest_node], path};  // pair of (diameter, path).
}

// 重み付き木の直径を求める.返り値は直径とその経路.O(|V|).
template <typename Type>
std::pair<Type, std::vector<int> > double_sweep(const std::vector<std::vector<std::pair<int, Type> > > &g, int s = 0) {
    const int vn = g.size();
    assert(0 <= s and s < vn);
    int furthest_node;
    std::vector<Type> d(vn);
    std::vector<int> pre(vn);
    std::queue<int> que;
    auto bfs = [&](int s) -> void {
        furthest_node = s;
        std::fill(pre.begin(), pre.end(), -1);
        d[s] = 0, pre[s] = -2;
        que.push(s);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            if(d[u] > d[furthest_node]) furthest_node = u;
            for(const auto &[v, cost] : g[u]) {
                assert(0 <= v and v < vn);
                if(pre[v] != -1) continue;
                d[v] = d[u] + cost, pre[v] = u;
                que.push(v);
            }
        }
    };
    bfs(s);
    bfs(furthest_node);
    std::vector<int> path({furthest_node});
    for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
    return {d[furthest_node], path};  // pair of (diameter, path).
}

}  // namespace algorithm
Back to top page