無向グラフ - 直径

概要

直径とは, 全点対の距離の中で最大の値を言う. ワーシャルフロイドは全点対の距離を求めるのでこれを使う. 計算量は \(O(V^3)\).

メモ

次の方法でも求まる.

1. 任意の点 \(s\) を選ぶ
2. \(s\) から距離が最大の点 \(t\) を探索する
3. \(t\) から距離が最大の点 \(u\) を探索する
4. \(t, u\) の間の距離が直径

距離が最大の点をダイクストラ法で求めることにすれば計算量は減る.

/// Graph - Undirected - Diameter
pub fn diameter(neigh: &Vec<Vec<usize>>) -> usize {
    let n = neigh.len();
    let mut d = vec![vec![n * 2 + 1; n]; n];
    for i in 0..n {
        d[i][i] = 0
    }
    for i in 0..n {
        for &j in neigh[i].iter() {
            d[i][j] = 1;
        }
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                let w = d[i][k] + d[k][j];
                if w < d[i][j] {
                    d[i][j] = w;
                }
            }
        }
    }
    (1..n)
        .map(|i| (0..i).map(|j| d[i][j]).max().unwrap())
        .max()
        .unwrap()
}

#[cfg(test)]
mod test_diameter {
    use crate::graph::undirected::diameter::*;
    #[test]
    fn cycle4() {
        assert_eq!(
            diameter(&vec![vec![3, 1], vec![0, 2], vec![1, 3], vec![2, 0],]),
            2
        );
    }
    #[test]
    fn cycle5() {
        assert_eq!(
            diameter(&vec![
                vec![4, 1],
                vec![0, 2],
                vec![1, 3],
                vec![2, 4],
                vec![3, 0],
            ]),
            2
        );
    }
    #[test]
    fn uni() {
        assert_eq!(
            diameter(&vec![vec![1, 2, 3, 4], vec![0], vec![0], vec![0], vec![0],]),
            2
        );
    }
}