トポロジカルソートとは？アルゴリズムの仕組みとC++実装例を解説

トポロジカルソートとは

トポロジカルソート（位相的整列）とは、有向非巡回グラフ（DAG：Directed Acyclic Graph）の頂点を線形順序に並べるアルゴリズムです。グラフ内のすべての辺 U → V に対して、並べた順序の中で頂点 u が必ず頂点 v より先に現れるように整列します。

始点側の頂点は終点側の頂点より先に処理される必要があるため、探索済みの頂点を一時的に保持するためにスタックを使用します。すべてのノードの処理が完了した後、スタックから要素を順に取り出して表示するだけで、トポロジカルな順序が得られます。

入力と出力

以下は、6つの頂点を持つグラフを隣接行列形式で入力した場合の実行例です。

入力：
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 1 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0

出力：
トポロジカルソート後のノード順：5 4 2 3 1 0

アルゴリズム

topoSort(u, visited, stack)

入力 − 開始頂点 u、各ノードが訪問済みかどうかを記録する配列、ノードを格納するスタック。
出力 − 頂点をトポロジカルな順序でスタックに格納します。

Begin
    u を訪問済みとしてマーク
    u に隣接するすべての頂点 v に対して、以下を実行
        v が未訪問の場合
            topoSort(v, visited, stack) を呼び出す
    done

    u をスタックにプッシュ
End

performTopologicalSorting(Graph)

入力 − 与えられた有向非巡回グラフ。
出力 − ノードの順序。

Begin
    最初にすべてのノードを未訪問としてマーク
    グラフのすべてのノード v に対して、以下を実行
        v が未訪問の場合
            topoSort(v, visited, stack) を呼び出す
    done
    スタックからすべての要素を取り出して表示
End.

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。深さ優先探索（DFS）を再帰的に行い、帰りがけの順でスタックへ頂点を積んでいくことで、トポロジカルソートを実現しています。

#include<iostream>
#include<stack>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0}
};

void topoSort(int u, bool visited[], stack<int>&stk) {
    visited[u] = true;              // ノードuを訪問済みとして設定

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {           // uに隣接するすべての頂点vに対して
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u);     // 開始頂点をスタックにプッシュ
}

void performTopologicalSort() {
    stack<int> stk;
    bool vis[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;     // 最初はすべてのノードが未訪問

    for(int i = 0; i<NODE; i++)
        if(!vis[i])         // ノードが未訪問の場合のみ探索
            topoSort(i, vis, stk);

    while(!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
}

main() {
    cout << "Nodes after topological sorted order: ";
    performTopologicalSort();
}

実行結果

Nodes after topological sorted order: 5 4 2 3 1 0

補足：計算量と注意点

このアルゴリズムは深さ優先探索（DFS）をベースとしており、隣接行列を使用した場合の時間計算量は O(V²)、隣接リストを使用した場合は O(V + E) となります（V は頂点数、E は辺数）。

また、トポロジカルソートはサイクルを持たない有向グラフ（DAG）に対してのみ定義可能です。グラフに閉路が含まれる場合、すべての頂点を矛盾なく線形順序に並べることはできないため注意が必要です。タスクの依存関係管理やビルドシステムなど、順序制約のある問題で広く活用されています。