有向非巡回グラフ(DAG)をトポロジカルソートする

有向非巡回グラフ(DAG)とは

DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。

トポロジカルソートとは

トポロジカルソートとは、グラフの有向辺の情報を満たすようにグラフを一列に並べることである。

トポロジカルソートの実装方法

トポロジカルソートは以下の操作で実装できる。

1. それぞれのノードにおいて入次数が0の物を取り出しcurrentNodeと名付ける
2. currentNodeをソート済みリストにaddする
3. currentNodeに隣接する(方向注意)ノードを取り出しnextNodeと名付ける
4. nextNodeの入次数を１下げる。
5. nextNodeの中から入次数が0のものをcurretNodeとして更新する
6. 2~4を繰り返す

入次数は隣接行列を元に配列で管理する。indegrees[i]はi番目のノードに関する入次数を表す。 ソート済みリストに追加されたノードは続く処理では考慮せずに考える。そのためcurrentNodeと隣接しているノードの入次数を下げる。これによってcurrentNodeを省いたグラフを見ることができ、再び入次数が0のノードが出現する。

ソースコード