Home > libalgo > トポロジカルソート

トポロジカルソート

概要

DAG が与えられたときに、全ての辺が右を向くように頂点を横一列に並べることをトポロジカルソートといいます．

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

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

計算量

$O(E+V)$

使い方

DAG ではないときは -1 一要素からなるリストが返る．

実装

std::vector<int> tsort(const Graph &g) {
    int n = g.size();
    enum State { NEW, ACTIVE, FINISHED };
    std::vector<int> res;
    vector<State> state(n, NEW);
    static const std::function<bool(int)> dfs = [&](int v) {
        state[v] = ACTIVE;
        for (auto &e : g[v]) {
            int w = e.dst;
            if (state[w] == ACTIVE)
                return false;
            else if (state[w] == NEW)
                if (!dfs(w)) return false;
        }
        state[v] = FINISHED;
        res.push_back(v);
        return true;
    };
    for (int i = 0; i < n; ++i)
        if (state[i] == NEW && !dfs(i)) return {-1};
    std::reverse(res.begin(), res.end());
    return res;
}

検証

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

参考文献

あり本