ホーム > libalgo

トポロジカルソート

概要

DAG の頂点をすべての辺が右を向くように並べることをトポロジカルソートといいます.

ある頂点 $v$ から到達可能かつ未到達の頂点を全てリストに追加したあとに $v$ を追加するとこを, 全ての頂点を訪問するまで繰り返します. すると,トポロジカル順序と逆順の列ができるので反転して返します.

実装で再帰関数を使っているのでスタックオーバーフローの可能性があります. これとは別に幅優先的な方法 (tsort.cc) もあります.

計算量

$O(E+V)$

実装

std::vector<int> tsort(const Graph &g) {
    int n = g.size();
    enum { YET, VISITED, DONE };
    std::vector<int> res, flg(n, YET);
    static const std::function<bool(int)> dfs = [&](int v) {
        flg[v] = VISITED;
        for (auto &e : g[v]) {
            int w = e.dst;
            if (flg[w] != DONE && (flg[w] == VISITED || !dfs(w))) return false;
        }
        flg[v] = DONE;
        res.push_back(v);
        return true;
    };
    for (int i = 0; i < n; ++i)
        if (flg[i] == YET && !dfs(i)) return {};
    std::reverse(res.begin(), res.end());
    return res;
}

検証

AOJ GRL4B http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2191897

参考文献

あり本