1. 序章

コンピューターサイエンスでは、有向非巡回グラフ（DAG）は、サイクルのない有向グラフです。このチュートリアルでは、線形時間でDAGのトポロジカルソートを作成する方法を示します。

2. トポロジカルソート

多くのアプリケーションでは、有向非巡回グラフを使用して、イベント間の優先順位を示します。 たとえば、スケジューリングの問題では、一連のタスクと、これらのタスクの順序を指定する一連の制約があります。 タスクを表すDAGを作成できます。 DAGの有向エッジは、タスクの順序を表します。

人がフォーマルな機会に服を着る方法の問題を考えてみましょう。 靴下、ズボン、靴など、いくつかの衣服を履く必要があります。 一部の衣服は、他の衣服よりも先に着用する必要があります。 たとえば、靴の前に靴下を履く必要があります。 靴下やズボンなど、一部の衣服は任意の順序で着用できます。 DAGを使用して、この問題を説明できます。

このDAGでは、頂点は衣服に対応します。 DAGの直接エッジは、衣服の前に衣服を着用する必要があることを示しています。 私たちの仕事は、依存関係の制約を尊重しながら、すべての衣服を着る順序を見つけることです。 たとえば、次の順序で衣服を着ることができます。

DAGのトポロジカルソートは、すべての頂点の線形順序付けであり、エッジが含まれている場合は、順序付けの前に表示されます。 DAGの場合、実行時間が線形のトポロジカルソートを構築できます。頂点の数とエッジの数、つまり。

3. カーンのアルゴリズム

DAGでは、グラフにサイクルが含まれていないため、2つの頂点間のパスの長さは有限です。 （ソース頂点）から （宛先頂点）までの最長パスとします。 は最長のパスであるため、への入力エッジはありません。 したがって、DAGには、入力エッジのない頂点が少なくとも1つ含まれています。

3.1. カーンのアルゴリズム

Kahnのアルゴリズムでは、入力エッジのない頂点を見つけることにより、DAGでトポロジカルソートを構築します。

このアルゴリズムでは、最初にすべての頂点の度内値を計算します。

次に、次数が0の頂点から開始し、それを出力リストの最後に配置します。 頂点を選択したら、頂点とその外側のエッジがグラフから削除されるため、隣接する頂点の次数の値を更新します。

すべての頂点を選択するまで、上記のプロセスを繰り返すことができます。 出力リストは、トポロジカルソートのグラフになります。

3.2. 時間計算量

すべての頂点の度数を計算するには、のすべての頂点とエッジにアクセスする必要があります。 したがって、実行時間は度内計算用です。 これらの値の再計算を回避するために、配列を使用してこれらの頂点の度内値を追跡できます。 while ループ内では、すべての頂点とエッジにもアクセスする必要があります。 したがって、全体の実行時間はです。

4. 深さ優先探索

深さ優先探索（DFS）アルゴリズムを使用して、トポロジカルソートを作成することもできます。

4.1。 再帰を使用したDFSのグラフ

DFSを使用してトポロジカルソートの側面に取り組む前に、標準の再帰グラフDFSトラバーサルアルゴリズムを確認することから始めましょう。

標準のDFSアルゴリズムでは、ランダムな頂点から開始し、この頂点を訪問済みとしてマークします。 次に、 dfsRecursive 関数を再帰的に呼び出して、アクセスされていない隣接するすべての頂点にアクセスします。 このようにして、時間内にすべての頂点を訪問できます。

ただし、各頂点にアクセスするとすぐにリストに追加され、どの頂点からでも開始できるため、標準のDFSアルゴリズムでは、トポロジカルソートされたリストの生成を保証できません。

この欠点に対処するために何をする必要があるか見てみましょう。

4.2. DFSベースのトポロジカルソートアルゴリズム

DFSアルゴリズムを変更して、トポロジカルソートのDAGを生成できます。 DFSトラバーサル中に、頂点のすべての隣接ノードにアクセスした後、結果リストの先頭に配置します。このように、ソートされたリストですべての隣接ノードの前に表示されることを確認できます。

このアルゴリズムは、標準のDFSアルゴリズムに似ています。 まだランダムな頂点から始めますが、一度アクセスした頂点をすぐにリストに追加することはありません。 代わりに、最初にすべての隣接ノードを再帰的に訪問してから、頂点をリストの先頭に配置します。 したがって、エッジが含まれている場合は、リストの前に表示されます。

DFSアルゴリズムと同じ時間計算量があるため、全体の実行時間もです。

5. 結論

この記事では、DAGでのトポロジカルソートの例を示しました。 また、トポロジカルソートを時間内に行うことができる2つのアルゴリズムについても説明しました。

DFSベースのトポロジカルソートアルゴリズムのJava実装は、Javaの深さ優先探索に関する記事で利用できます。