📝

トポロジカルソート -Kahn's Algorithm-

2025/10/23に公開

はじめに

記事を書いて欲しいというリクエストがあってトポロジカルソートについて学習してみました！
普段無向グラフの閉路判定を何も考えずにUnionFindでやってしまっていたのですが、有向グラフに太刀打ちできなそうだったので有向グラフの閉路判定法であるトポロジカルソートについて学ぶ良い機会になりました。使用する言語はC++です。

こんなことを前に書くのもアレですが、、
前もって書いておきますが別にこのアルゴリズムは強いアルゴリズムじゃないです。結果的に有向非巡回グラフから
閉路があるか判定
することができるだけで、

閉路の場所
閉路の長さ

などを特定できるわけではありません。

トポロジカルソートとは

有向非巡回グラフ(Directed Acyclic Graph, DAG）の各ノードを順序付けして, どのノードもその出力辺の先のノードより前にくるように並べることである. 依存関係のあるタスクの実行順序の決定などで使われる.
具体的には,

のように有向非巡回グラフを,

このように左向きの矢印がないように一列に並びかえるのが目標である.
並び替えた列をトポロジカル順序という.

Kahn's Algorithm

ソートの手順

ある頂点についてそこに入ってくる辺の本数を表す用語として "入次数(いりじすう)" を導入する.
ロジックとしては, 幅優先探索の要領で探索順序を決定していく. 具体的な手順は,

ある頂点について入ってくる辺の数が0ならば, それより左に未ソートの頂点がないのでその時点での1番左に並べていくことができる.
それを一番左に並べた時点でその頂点から出てる辺を削除できる. (もうその頂点を探索済みにして依存関係を消せるから)
1.(入次数0のチェック)に戻る.

を繰り返していく.
全ての辺, 頂点を一度ずつ処理するので, 時間計算量も空間計算量も $O(|V|+|E|)$ である.

なおソート後の最終形には一意性はなく入次数が0となった時にどの頂点を先に処理するかで結果は変わる. 裏を返せば入次数が0の頂点が同時に二つ以上生じなければトポロジカル順序は一意に定まる. (コードでいうと常にqueue.size()==1が成立する. )

具体例

これをソートしていく.

まず頂点1に入ってくる辺がないので, queueに1を入れる.
queueの先頭1をグラフから削除して答えの配列の頂点1を先頭にする. この時頂点1についている全ての辺も削除する.

こうなる. そうすると, 頂点2, 3も入次数が0なので処理待ちの列に入れる.
queueは{2, 3}となる.
頂点2を削除する.

頂点4が入次数0になったのでqueueに入れる. 中身は{3, 4}
頂点3を削除する.

頂点6が入次数0になったのでqueueに入れる. 中身は{4, 6}
頂点4を削除する.

queueの中身は{6}なので続いて頂点6を削除する.

頂点5, 7も同じように処理していくと,

という風にトポロジカル順序を得ることができる.
ちなみに

もトポロジカル順序の一つなので一意性はないこともわかる.

実装

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N),edges(M, vector<int> (2));
    vector<int> indeg(N), ans;
    for (auto edge : edges) {
        G[edge[0]].push_back(edge[1]);
        indeg[edge[1]]++;
    }
    queue<int> Q;
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0) {
            Q.push(i);
        }
    }
    while (!Q.empty()) {
        int pos = Q.front();
        Q.pop();
        ans.push_back(pos);
        for (auto next : G[pos]) {
            indeg[next]--;
            if (indeg[next] == 0) {
                Q.push(next);
            }
        }
    }
    return 0;
}

コード解説

    int N, M;
    vector<vector<int>> G(N),edges(M, vector<int> (2));
    vector<int> indeg(N), ans;

ここら辺は頂点数N, 辺の数M, 頂点iから出る辺を格納する二次元配列G, 有向辺を保管する二次元配列edgesを用意している.
$i$ 番目の辺はedges[i][0]→edges[i][1]の有向辺であることを示す.
各頂点に対して入ってくる辺の本数(入次数)を格納するindeg, トポロジカル順序を格納するansも用意する.

    for (auto edge : edges) {
        G[edge[0]].push_back(edge[1]);
        indeg[edge[1]]++;
    }

の部分ではG,edges, indegの定義通りに値を格納している.

    queue<int> Q;
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0) {
            Q.push(i);
        }
    }

探索すべき頂点を保管するキューQを用意して, 入次数が0の頂点を格納する.

    while (!Q.empty()) {
        int pos = Q.front();
        Q.pop();
        ans.push_back(pos);
        for (auto next : G[pos]) {
            indeg[next]--;
            if (indeg[next] == 0) {
                Q.push(next);
            }
        }
    }

あとはキューに中身がある限り, キューの先頭の頂点を削除し, その頂点から有向辺が向かう頂点の入次数を1減らして入次数が0になればキューに入れる. というのを繰り返していく.

閉路判定

全ての頂点がトポロジカルソートされたかどうかで閉路があるかを判定することができる.
コードでいうとans.size()と頂点数Nがを比較すると閉路があるかどうか判定できる.
ans.size() < Nの時ソートされていない頂点が残っている, つまり, 入次数が０の頂点がもうないのでこれは閉路を形成している.

まとめると,
ans.size() < Nのとき閉路があり,
ans.size() == Nが成り立つ時閉路は存在しない.

閉路がある場合の具体例

さっきの例と同様に頂点1, 2, 3を処理する.

ここで先ほどと違い頂点4には頂点5からの辺があるので入次数0の辺が存在しない.
この時点でトポロジカルソートをこれ以上進めることはできない. というわけでこれがans.size() (= 3) < N (= 7)という状態である.

ちなみに, これをきちんと考えたい方向けに一番最後に証明を載せておきました。読みたい方はどうぞ

例題

証明

あんまり証明が見当たらなかったので証明してみました。

$グラフGについて$
$「Gがトポロジカルソート可能」\Leftrightarrow 「Gは有向非巡回グラフ(DAG)である」$
を示していく.

$(\Rightarrow )$
$G$ が有向であることは自明である. 非巡回であることを示す.
$G$ はトポロジカルソートできるのでトポロジカル順序

v_1,v_2,...,v_n

が存在する.
背理法を用いて示す.

G

に有向閉路

C(v_s→v_{s+1}→...→v_t→v_s)

が存在すると仮定する. するとこの時,

v_s

より前に

v_s

が存在することになり矛盾.
よって仮定が誤っており

G

に有向閉路は存在しない.
以上よりGは有向非巡回グラフ(DAG)である.
つまり,

「Gがトポロジカルソート可能」\Rightarrow 「Gは有向非巡回グラフ(DAG)である」

が示された.

$(\Leftarrow )$
$G$ の頂点の集合を $V$ , 辺の集合を $E$ とする.

前提として有限な有向グラフ $G$ には少なくとも1つ入次数が0の頂点が存在する.

補題(有限なDAGに入次数0の頂点が存在する)証明

対偶「グラフ $G$ のどの頂点も入次数が1以上」 $\Rightarrow$ 「グラフ $G$ には有向閉路が存在する」
を証明する.
頂点の数は $|V|$ , 辺の数は $|E|$ であり, この時全ての頂点について入次数が1以上なので

|V|\le |E|

が成立する. (有限の過程より

|V|\lt \infty

)
ある頂点

v_1

について入次数が1以上なので

v_1

に向かう有向辺を持つ頂点

v_2

が存在する. 同様に

v_2

に向かう有向辺を持つ頂点

v_3

が存在する. 繰り返していくと

E

回この議論を行うことができる. ここで

|V|\le |E|

なので, この議論は

|V|

回以上行われており, 鳩の巣原理より2回議論に登場する頂点が必ず一つ以上存在する. よってここに有向閉路が存在する.
よって対偶が真であることが証明されたので元の命題
「有限な有向グラフ

G

には少なくとも1つ入次数が0の頂点が存在する」も真である.

頂点の数 $|V|$ に対して数学的帰納法を用いて証明していく.
$V=0,1$ の時は自明でトポロジカルソートが可能である.
$|V|<n$ の任意の有向非巡回グラフ $G$ に対してトポロジカルソートが可能であると仮定する.
この時補題より入次数0の頂点 $v_0$ が存在する. ここで頂点 $v_0$ とそこから出る辺を削除してできるグラフを $G'=(V', E')$ とする. $|V'|=n-1$ である. $G'$ は $G$ の部分グラフであるので閉路を含まない. ( $G$ に閉路がないので)
よって仮定よりこのグラフ $G'$ はトポロジカルソート可能である. あるトポロジカル順序を

v_1,v_2,...,v_{n-1}

としたときにこの先頭に

v_0

をつけると

v_0,v_1,v_2,...,v_{n-1}

という順番になり, 元のグラフ

G

について

v_0

の入次数は0であり,

v_1,v_2,...,v_{n-1}

の部分はトポロジカル順序である(トポロジカルソート可能の)仮定があるので

v_0,v_1,v_2,...,v_{n-1}

この列はトポロジカル順序である. (トポロジカルソート可能の条件を満たす.)
よって

|V|<n

の命題の成立の仮定のもとで

|V|=n

の命題の成立が確認できたので数学的帰納法より,

「Gがトポロジカルソート可能」\Leftarrow 「Gは有向非巡回グラフ(DAG)である」

が示された.

以上の議論より,
$「Gがトポロジカルソート可能」\Leftrightarrow 「Gは有向非巡回グラフ(DAG)である」$
である.

最後に

理論だけではわかりいくい部分もありましたが実際にグラフを書いてみたりコードを書いてみると意外とスッと理解することができました。解けなかった問題も解けるようになって嬉しかったです。
わかりにくかったり、間違っている部分があったらぜひ教えてください！
それと、トポロジカルソートはリクエストがあって学習したのですが本当に理解を進めていくのが楽しいアルゴリズムでした！どんどん吸収して解説していくのでぜひ扱って欲しい題材があればリクエストしてください！！