DAG

有向非巡回グラフ(DAG)は、ノードの集合と有向辺の集合から構成されるグラフ構造の一種です。各辺には方向があり、あるノードから別のノードを指します。また、グラフには閉路が含まれません(つまり、あるノードから始めて有向辺をたどり、同じノードに戻ることはできません)。したがって、DAGは閉路のない有向グラフです。

DAGは、タスクスケジューリング、コンパイラ最適化、依存関係分析など、さまざまな分野で広く応用されています。これらの応用では、DAGは通常、タスク間の依存関係や計算プロセス内のデータフローを表現するために用いられます。

トポロジカルソート

トポロジカルソートは、グラフ理論やプロジェクト管理において、有向非巡回グラフ(DAG)のノード(またはタスク)を線形に順序付けるために用いられる基本的なアルゴリズムです。トポロジカルソートの目的は、すべての有向辺(u, v)に対してノードuが線形順序でノードvより前に現れるようにノードを並べることです。言い換えれば、依存関係を尊重しつつ、タスクの完了や要素の処理に対して一貫した順序を確立します。

トポロジカルソートに関する要点:

  1. 有向非巡回グラフ(DAG):トポロジカルソートは、閉路のない有向グラフにのみ適用できます。閉路があるとタスクの順序に曖昧さが生じ、トポロジカル順序が不可能になるためです。

  2. 依存関係の解決:トポロジカルソートは、依存関係を持つ一連のタスクや活動がある場合に特に有用です。これにより、タスクが正しい順序で実行されることが保証され、他のタスクに依存するタスクがその前提条件の完了前に開始されることはありません。

  3. 応用例:

    • プロジェクト管理:トポロジカルソートは、プロジェクト内のタスクをスケジュールし、プロジェクトが期限内に完了することを保証するのに役立ちます。
    • コンパイラ最適化:コンパイラ設計において、コード生成やプログラムセグメントの最適化に最適な順序を決定するのに役立ちます。
    • 依存関係分析:ソフトウェアエンジニアリングにおいて、モジュール、関数、クラス間の依存関係を分析するために用いられます。
    • 履修計画:教育機関において、前提条件に基づいて科目をスケジュールするのに役立ちます。
  4. アルゴリズム:トポロジカルソートを実行できるアルゴリズムはいくつかあります。深さ優先探索(DFS)と幅優先探索(BFS)が一般的に用いられる手法です。アルゴリズムの選択は、問題の具体的な要件によって異なります。

  5. クリティカルパス:トポロジカルソートは、プロジェクトにおけるクリティカルパス、すなわちグラフを通る最長の経路を特定することもできます。クリティカルパス上のタスクは、遅延するとプロジェクト全体が遅延するタスクです。

  6. 複数の有効な順序:特定のDAGにおいて、複数の有効なトポロジカル順序が存在し得ることに注意することが重要です。この柔軟性により、最適化、並列処理、リソース割り当てが可能になります。

全体として、トポロジカルソートは、有向非巡回グラフが広く見られるさまざまな応用において、依存関係を管理し、タスクが正しい順序で実行されることを保証するための強力なツールです。

有向非巡回グラフ(DAG)に対してトポロジカルソートを行う際に一般的に用いられるアルゴリズムは2つあります。深さ優先探索(DFS)と幅優先探索(BFS)です。どちらのアルゴリズムも、グラフ内のノードに対して有効なトポロジカル順序を見つけるために使用できます。以下に各アルゴリズムについて説明します。

  1. 深さ優先探索(DFS)アルゴリズム:

    • DAG内の任意のノードから開始します。
    • グラフの深さ優先探索を実行し、ノードを訪問済みとしてマークします。
    • 未訪問の隣接ノードがないノード(すなわち葉ノード)に到達したら、そのノードをトポロジカル順序の先頭に追加します。
    • すべてのノードが訪問されるまでこの処理を続けます。

    DFSに基づくトポロジカルソートアルゴリズムの擬似コード:

    function topologicalSort(graph):
        order = []
        visited = set()
    
        for each node in graph:
            if node is not visited:
                visit(node, order, visited)
    
        return reverse(order)
    
    function visit(node, order, visited):
        mark node as visited
        for each neighbor of node:
            if neighbor is not visited:
                visit(neighbor, order, visited)
        append node to order
  2. 幅優先探索(BFS)アルゴリズム:

    • 空のキューと、トポロジカル順序を格納するリストを初期化します。
    • まず、入ってくる辺を持たない(入次数が0の)すべてのノードをキューに追加します。
    • キューにノードがある間、次の処理を行います:
      • ノードを1つキューから取り出し、トポロジカル順序リストに追加します。
      • その各隣接ノードについて、入次数を1減らします。
      • 隣接ノードの入次数が0になった場合、その隣接ノードをキューに追加します。
    • キューが空になるまで、上記の処理を繰り返します。

    BFSベースのトポロジカルソートアルゴリズムの擬似コード:

    function topologicalSort(graph):
        order = []
        queue = empty queue
    
        for each node in graph:
            if in-degree of node is 0:
                enqueue(node)
    
        while queue is not empty:
            node = dequeue(queue)
            append node to order
            for each neighbor of node:
                reduce in-degree of neighbor by 1
                if in-degree of neighbor is 0:
                    enqueue(neighbor)
    
        return order

DFSベースとBFSベースのいずれのアルゴリズムも、DAGに対して有効なトポロジカル順序を生成します。どちらを選択するかは、性能や問題の具体的な要件などの要因によって決まります。

V = n、E = m のとき、Gのトポロジカルソートの計算量は O(n+m) です