Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

閉路検出アルゴリズム

ABC139のEで閉路の話が出てきたので、閉路について調べようと思いました。

UFを使って無向グラフの閉路を検出するアルゴリズム

知らなかったです;;

www.youtube.com

無向グラフにおいて閉路検出する方法は、有向グラフと見てDFSでやっていくというのが一つ浮かびますが、UFを使って実装することも出来るようです。

UF上で辺を一本一本つないでいく。この時、sとtをつなぐとして、こいつらがもしすでに同じグループに入っていたら、無向グラフなので明らかにループするというアイデアによって閉路を検出出来ます。

有向グラフにおいて閉路を検出するアルゴリズム

一番シンプルなのは、in degreeが0のものからDFSしていくという方針だと思いますが、

www.youtube.com

このビデオで紹介されているwhite set, gray set, black setというのを使うアルゴリズムは等価でしょうか?

とりあえず実装しています。GRL_4_Aでverifyしました。しかしこの実装は再帰しているので、Nが大きい場合には使えないと思います。

pub fn cycle_detection_directed_textbook(g: &[Vec<usize>]) -> bool {
    let mut white_set = HashSet::new();
    let mut gray_set = HashSet::new();
    let mut black_set = HashSet::new();

    for v in 0..g.len() {
        white_set.insert(v);
    }
    while !white_set.is_empty() {
        while let Some(cur) = white_set.iter().cloned().next() {
            if dfs(g, cur, &mut white_set, &mut gray_set, &mut black_set) {
                return true
            }
        }
    }

    return false;

    fn dfs(g: &[Vec<usize>], cur: usize, white_set: &mut HashSet<usize>, gray_set: &mut HashSet<usize>, black_set: &mut HashSet<usize>) -> bool {
        moveVertex(cur, white_set, gray_set);
        for neighbour in g[cur].iter().cloned() {
            if black_set.contains(&neighbour) {
                continue;
            }
            if gray_set.contains(&neighbour) {
                return true
            }
            if dfs(g, neighbour, white_set, gray_set, black_set) {
                return true
            }
        }
        moveVertex(cur, gray_set, black_set);
        false
    }

    fn moveVertex(v: usize, from: &mut HashSet<usize>, to: &mut HashSet<usize>) {
        from.remove(&v);
        to.insert(v);
    }
}