ホーム > libalgo

トポロジカルソート (Kahn)

概要

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

まず,入次数が 0 の頂点 $v$ は列の一番左に追加できます. 次に,$v$ と $v$ から伸びる辺を取り除きます. そのとき入次数が 0 となる頂点は,取り除いてリストの $v$ の末尾に追加できます. この操作を,全ての頂点が取り除かれるまで繰り返します. 下の実装ではリストに追加できる頂点をキューで管理するので幅優先探索みたいになります.

これとは別に,深さ優先探索を行う方法 (tsort-dfs.cc) もあります.

計算量

$O(E+V)$

実装

std::vector<int> tsort(const Graph &g) {
    int n = g.size(), k = 0;
    std::vector<int> ord(n), in(n);
    for (auto &es : g)
        for (auto &e : es) in[e.dst]++;
    std::queue<int> q;
    for (int i = 0; i < n; ++i)
        if (in[i] == 0) q.push(i);
    while (q.size()) {
        int v = q.front();
        q.pop();
        ord[k++] = v;
        for (auto &e : g[v])
            if (--in[e.dst] == 0) q.push(e.dst);
    }
    return *std::max_element(in.begin(), in.end()) == 0 ? ord : std::vector<int>();
}

検証

参考文献

Topological sorting - Wikipedia, the free encyclopedia