DAG（有向非巡回グラフ）のランダム線形拡張を生成するC++プログラム

この記事では、有向非巡回グラフ（DAG: Directed Acyclic Graph）のランダム線形拡張（Random Linear Extension）を作成する方法を解説します。線形拡張とは、DAGの位相ソート（トポロジカルソート）に相当するものです。以下のようなグラフを例に考えてみましょう。

トポロジカルソートとは

有向非巡回グラフにおけるトポロジカルソートとは、頂点を線形に並べた順序のことです。有向グラフのすべての辺 u-v に対して、並び順の中で頂点 u が必ず頂点 v よりも先に現れるような順序を指します。

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

入力

出力

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

アルゴリズム

topoSort(u, visited, stack)

入力 − 開始頂点 u、訪問済みかどうかを記録する配列、ノードを格納するスタック。

出力 − 頂点をトポロジカル順にスタックへ格納します。

Begin
    mark u as visited
    for all vertices v which is adjacent with u, do
        if v is not visited, then
            topoSort(c, visited, stack)
        done
        push u into stack
End

performTopologicalSorting(Graph)

入力 − 与えられた有向非巡回グラフ。

出力 − ノードの順序。

Begin
    initially mark all nodes as unvisited
    for all nodes v of the graph, do
        if v is not visited, then
            topoSort(i, visited, stack)
        done
        pop and print all elements from the stack
End

サンプルコード（C++）

以下は、再帰的な深さ優先探索（DFS）とスタックを組み合わせてトポロジカルソートを実装したC++のサンプルコードです。計算量は頂点数を V、辺数を E とすると O(V + E) になります。

#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; //set as the node v is visited
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]){ //for allvertices v adjacent to u
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u); //push starting vertex into the stack
}
void performTopologicalSort() {
    stack<int> stk;
    bool vis[NODE];
    for(int i = 0; i<NODE; i++)
        vis[i] = false; //initially all nodes are unvisited
    for(int i = 0; i<NODE; i++)
        if(!vis[i]) //when node is not visited
            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