トポロジカルソート

トポロジカルソートについて解説する。

トポロジカルソートとは

有向無閉路グラフにおいて頂点の並びであって、任意の辺に対してその辺が順方向に進むものへと並び替えることである。つまり、 頂点列(v{k_i})で任意の辺(v, v')においてv = v{k_i}, v' = v_{k_i'}とすると、i < i'が成り立つことである。

以下のアルゴリズムである。

1. 入次数が0の頂点のなかで任意に一つ選ぶ。
2. 選んだ頂点を取り除いたグラフで1と同様のことをする。

この時に取り出された順に頂点を並べるとトポロジカルソートとなる。逆にこの方法以外ではトポロジカルソートを作ることはできない。

証明

入次数0の頂点を有効無閉路グラフからとると、それはまた有効無閉路グラフである。これと実際に考えたときに得られたソートがトポロジカルソートであることは明らかである。（これでいいのか。）

実装

let mut e = vec![vec![]; n];
let mut last = vec![0; n];
for &(a, b) in &ab {
    e[a].push(b);
    last[b] += 1;
}
let mut h = std::collections::BinaryHeap::new();
for i in 0..n {
    if last[i] == 0 {
        h.push(Reverse(i));
    }
}

let mut ans = vec![];
let mut used = vec![false; n];
while let Some(Reverse(i)) = h.pop() {
    if used[i] {
        continue;
    }
    ans.push(i);
    used[i] = true;
    for &j in &e[i] {
        last[j] -= 1;
        if last[j] == 0 {
            h.push(Reverse(j));
        }
    }
}

これはトポロジカルソートの結果の中で辞書順で最も小さなものを出力している。

通常のトポロジカルソートは計算量としてO(N + E)となる。トポロジカルソート可能であることと有向無閉路グラフであることは同値であるので、閉路があるかないかをトポロジカルソート可能か不可能かで見ることができる。が、しかし、DFSでもBFSでもできるのでとてもあんまり意味がない。