日常の例を使ってトポロジカルソートの原理を分かりやすく解説します！【経営工学を専門にしている大学生の日記】

こんにちは！しゅんです！

トポロジカルソートはグラフ理論で登場する用語で、各要素の依存関係を分かりやすく表すことができます。

この記事ではトポロジカルソートというアルゴリズムについて、基本的な考え方や実装方法を分かりやすく解説していきます。

また今回はpythonを使って実際にトポロジカルソートを実装していきたいと思います。

それでは解説していきましょう！

他のソートについてはこちらの記事で解説しています！

2023年4月21日 ヒープソートの原理を分かりやすく解説します！【経営工学を専門にしている大学生の日記】

2023年4月11日 マージソートの原理を分かりやすく解説します！【経営工学を専門にしている大学生の日記】

2023年4月25日 カウントソートの原理を分かりやすく解説します！【経営工学を専門にしている大学生の日記】

下にあるグラフを考えてみましょう。

このグラフを使ってトポロジカルソートについて説明したいと思います。青で書かれているのが頂点の情報です。頂点には1から6というラベルを付けておきます。


黒で書かれているのが辺の情報です。矢印は辺の方向を表しています。例えば頂点2と頂点4の間の辺を見てみましょう。この辺は2から4にしか行くことができないということです。


トポロジカルソートで気にするのは辺の向きです。この辺の向きが一方向になるように並べ替えることをトポロジカルソートと言います。例えば上のグラフをトポロジカルソートすると下のようになります。

1→2→3→5→4→6の順番で並べ替えました。矢印は元のグラフの矢印と同じように配置しています。（大きさは関係ないです。）矢印の向きが全部左から右に向かっていますね。このように並び替えることをトポロジカルソートと言います。例えば下の順番はトポロジカルソートとはなりません。

1→2→5→3→4→6の順番で並べ替えました。5と3の間を見てみると、一つだけ右方向に矢印が向かっていますね。このように矢印の方向が違う者が入っているので上の並べ方はトポロジカルソートではありません。

有向グラフであること

トポロジカルソートは特定の条件下でしか使えません。まず1つ目は有向グラフであることです。これは直観的にも分かりやすいと思います。


要は頂点同士を結ぶ辺に方向がなきゃだめだということです。

非巡回グラフであること

2つ目の条件は非巡回グラフであることです。非巡回グラフとはグラフ中に閉路がないということです。つまりどの頂点から有向辺をたどっていっても元の頂点に戻ってこれないグラフのことです。

上のグラフのNG例を見てると1をスタートとして1→4→3→2→1の順番にたどっていくことで再び1にたどり着くことができています。このようにグラフ中に閉路がある巡回グラフではトポロジカルソートを使うことができません。


有向非巡回グラフのことをDAG(Directed Acyclic Graph)といいます。

トポロジカルソートの目的はグラフ中における頂点同士の依存関係を明らかにすることです。例えば上の例で言うと、頂点1からは頂点2と頂点3に矢印が伸びていますね。これは頂点1が先に処理されてから頂点2、頂点3が処理されると言うことを表します。


例えば「洗濯」をグラフ理論を用いて分析する場合を考えてみましょう。頂点1が「洗剤を入れる」、頂点2が「洗濯機を回す」だと仮定すると、頂点1から頂点2に矢印が伸びるはずです。なぜなら「洗剤を入れる」という処理が実行されないと「洗濯機を回す」ことができないからです。

このように複数の処理がある場合に、それらの依存関係を明らかにして分析しやすくするのがトポロジカルソートの目的です。

ここで一つ日常の例を使ってトポロジカルソートを解説していきます。今回は「味噌汁を作る」ことに対してグラフを作ってトポロジカルソートをやっていこうと思います。


まず初めに味噌汁を作る手順を以下のように決めたいと思います。

頂点の番号も上のようにしてグラフを作っていきます。グラフは以下のようになります。

これをトポロジカルソートすると以下のようになります。

トポロジカルソートを適用すると1→3→2→4→5→6→7という順番になります。（2と4の位置を入れ替えてもOKです。）例えば3,2,4は5に矢印が伸びていますが、これは3,2,4の処理が実行されないと5の処理を実行することができないということです。


2,3,4は各具材を切る処理で5は鍋に具材を入れる処理なので、つまり具材を切ってからじゃないと鍋に入れることができないということを表しています。


ぶっちゃけ味噌汁を作るというような簡単な手順ではトポロジカルソートがどうすごいのかが伝わりにくいですが、例えば銀行のシステムや企業の大規模プロジェクトといった手順が非常に複雑なシステムを分析する場合には非常に有用です。

最後にpythonでトポロジカルソートを実装してみたいと思います。以下がコードの例です。

def topological_sort(graph):
    # 初期化
    in_degree = {node: 0 for node in graph}  # 各ノードの入次数を初期化
    queue = []  # 入次数が0のノードを保持するキュー
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1  # 各ノードの入次数を計算
    for node in graph:
        if in_degree[node] == 0:
            queue.append(node)  # 入次数が0のノードをキューに追加

    # トポロジカルソートの実行
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)  # ソートされた結果にノードを追加
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # 入次数を減らす
            if in_degree[neighbor] == 0:
                queue.append(neighbor)  # 入次数が0になったらキューに追加

    # グラフにサイクルがある場合は例外を発生させる
    if len(result) != len(graph):
        raise ValueError("Graph contains at least one cycle")
    return result

このコードは隣接リストが入力されたときに非巡回グラフだったらトポロジカルソートされた頂点リストを返し、閉路（サイクル）がある場合はエラーを返す関数です。


隣接リストとは、ある頂点と隣接してる頂点を格納しているリストです。例えば頂点1から出ている矢印が頂点2,頂点3に繋がっているときは1:[2,3]と表します。


このプログラムを使って下の複雑なグラフをトポロジカルソートしてみましょう。

このグラフを隣接リストで表すと以下のようになります。

graph = {
         1:[2,3,4],
         2:[3],
         3:[5],
         4:[2,5,6,9],
         5:[],
         6:[3,5,8,9,11],
         7:[10],
         8:[7,10],
         9:[8,11],
         10:[],
         11:[10]
}

例えば1の所を見ると2,3,4が格納されていますが、これは頂点1からは頂点2,頂点3,頂点4に繋がっていると言うことを表しています。それではトポロジカルソートを実行してみましょう。

topological_sort(graph)

ということでトポロジカルソートを実行することができました。このように複雑なグラフになってもプログラミングをすればトポロジカルソートを実行することができます。

いかがでしたか。

今回の記事ではトポロジカルソートについて解説していきました。

今後もこのような経営工学に関する記事を書いていきます！

最後までこの記事を読んでくれてありがとうございました。