有向グラフでのサイクルの検出
1. 序章
有向グラフは通常、実際のアプリケーションで一連の依存関係を表すために使用されます。 たとえば、クラススケジュールの前提条件となるコースは、有向グラフを使用して表すことができます。
そして、この種のグラフのサイクルはデッドロックを意味します。つまり、最初のタスクを実行するには2番目のタスクを待機し、2番目のタスクを実行するには最初のタスクを待機することを意味します。 したがって、サイクルを検出することは、どのアプリケーションでもこの状況を回避するために非常に重要です。
2. 問題の説明
有向グラフで、サイクルを見つけたいと思います。 これらのサイクルは、次のように、1つの頂点がそれ自体に接続されているか、2つの頂点が接続されているかのように単純です。
または、次の例に示すような、より大きなサイクルを持つことができます。ここで、サイクルはBCDEです。
また、示されているように、互いに交差する複数のサイクルを持つグラフを取得できます（ABCED、BCED、およびEDFの3つのサイクルがあります）。
また、これまでのすべての例では、任意のノードからグラフをトラバースすると、すべてのサイクルを見つけることができることに注意してください。 ただし、これはすべてのグラフに当てはまるわけではありません。
一部のグラフでは、次の例に示すように、さまざまなポイントからグラフにアクセスして、グラフのようにすべてのサイクルを見つける必要があります（サイクルはCDEとGHです）。
3. アルゴリズムのアイデア
この記事の最初の2つの例のように、単純なグラフでサイクルを見つけるのは簡単です。 すべての頂点をトラバースして、それらのいずれかがそれ自体に接続されているか、またはそれに接続されている別の頂点に接続されているかどうかを確認できます。 しかし、もちろん、これはより複雑なシナリオでは機能しません。
したがって、サイクルを見つけるための有名な方法の1つは、深さ優先探索（DFS）を使用することです。 DFSを使用してグラフをトラバースすると、DFSツリーと呼ばれるものが得られます。 DFSツリーは、主にグラフの頂点とエッジの並べ替えです。 また、 DFSツリーを構築した後、エッジはツリーエッジ、前方エッジ、後方エッジ、およびクロスエッジに分類されます。
2番目のグラフに基づく例を見てみましょう。
前の例では、エッジEBがバックエッジとしてマークされていることがわかります。 バックエッジは、頂点の1つをDFSツリー内のその親の1つに接続しているエッジです。
前の例では、エッジACも前縁としてマークされています。 フォワードエッジは、親をDFSツリーの非直接の子の1つに接続するエッジです。
グラフの実線にも通常のエッジがあることに注意してください。 これらの実線のエッジはツリーのエッジです。
複数のバックエッジがある別の例を見てみましょう。
各バックエッジで、グラフでサイクルを識別できることに注意してください。 したがって、グラフの後ろのエッジを削除すると、DAG（有向非巡回グラフ）を作成できます。
次に、直面する可能性のある別の問題を説明するための最後の例を1つ見てみましょう。
この最後の例では、クロスエッジとしてマークされたエッジを見ることができます。
この部分を理解するには、与えられたグラフのDFSについて考える必要があります。 このグラフで頂点AからDFSを開始すると、頂点A、C、D、E、およびFにアクセスします。
それでも、頂点B、G、およびHは表示されません。 したがって、この場合、頂点Bなど、アクセスされなかった別のポイントからの最初の実行後にDFSを再起動する必要があります。 これらの複数のDFS実行の結果として、複数のDFSツリーが作成されます。
この例のアイデアを結論付けるために、1つのグラフに複数のDFSツリーを含めることができます。 また、クロスエッジは、この例では、グラフのDFSツリーの1つから別のDFSツリーに頂点を接続するエッジです。
親と子（ツリーの異なるブランチ間のエッジ）を接続しない場合、クロスエッジも同じDFSツリー内にある可能性があります。
ただし、このチュートリアルでは、有向グラフのサイクルを示すため、主にDFSツリーのバックエッジに関心があります。
4. フローチャート
主なアイデアは、いくつかの変更を加えたDFS問題として簡単に説明できます。 最初に、次のフローチャートに示すように、グラフ内の未訪問の各頂点からDFSを繰り返すようにします。
2番目の部分は、DFS処理自体です。 この部分では、バックエッジをチェックできるように、DFSのスタックにあるものにアクセスできることを確認する必要があります。
そして、スタック内のある頂点に接続されている頂点を見つけると、1つのサイクル（または複数のサイクル）が見つかったことがわかります。
最初のサイクルを印刷することが目標である場合は、図のフローチャートを使用して、DFSスタックと一時スタックを使用してサイクルを印刷できます。
ただし、グラフを非巡回グラフに変換することが目標である場合は、サイクルを印刷しないでください（すべてのサイクルを印刷することはNP困難な問題であるため）。
代わりに、グラフで見つかったすべてのバックエッジをマークして削除する必要があります。
5. 擬似コード
このチュートリアルの次の部分は、有向グラフのサイクルを検出するための単純な擬似コードです。
このアルゴリズムでは、入力は有向グラフです。 簡単にするために、隣接リストを使用していると仮定できます。
最初の関数は、グラフを読み取り、最初にNOT_VISITEDとしてマークされたグラフ頂点（この擬似コードでは visited と呼ばれます）のフラグのリストを作成する反復関数です。
次に、関数はすべての頂点を反復処理し、新しい NOT_VISITED 頂点を見つけると、関数processDFSTreeを呼び出します。
processDFSTree 関数は、グラフ、訪問先リスト、およびスタックの3つの入力を受け取る再帰関数です。 その後、関数は主にDFSを実行しますが、最初に見つかったときに、見つかった頂点をIN_STACKとしてマークします。
そして、頂点を処理した後、それをDONEとしてマークします。 IN_STACK、である頂点が見つかった場合、バックエッジが見つかりました。これは、サイクル（または複数のサイクル）。
したがって、サイクルを印刷するか、後端にマークを付けることができます。
最後に、サイクルを出力する関数を記述しましょう。
印刷機能には、主に後端で見つかったスタックと頂点が必要です。 次に、関数はスタックから要素をポップして出力し、一時スタックを使用して要素をプッシュバックします。
6. 複雑
与えられたアルゴリズムの時間計算量は主にDFSであり、これはです。
スペースの複雑さについては、頂点のマーキングとスタックにスペースを割り当てる必要があるため、の順序になります。
7. 結論
このチュートリアルでは、有向グラフでサイクルを検出するためのアルゴリズムの1つについて説明しました。 最初に、このアルゴリズムの重要なアプリケーションの1つについて説明しました。 次に、アイデアを説明し、例、フローチャート、および擬似コードを使用して、一般的なアルゴリズムのアイデアを示しました。
最後に、アルゴリズムの平均的な空間と時間の複雑さを示しました。
