無向グラフのサイクル

1. 概要

このチュートリアルでは、深さ優先探索（DFS）を使用して無向グラフでサイクルを検出する方法を学習します。

グラフは、制限された頂点（またはノード）のセットと、これらの頂点を接続するエッジのセットで構成されるデータ構造です。

頂点のセットとエッジのセットを使用して、グラフを定義できます。すべてのエッジは2つの頂点を接続し、接続された頂点であるとして表示できます。

たとえば、2つの頂点との間にエッジがある場合、それらを関連付け済みと呼びます。次に、これら2つを隣接する（隣接する）頂点と呼ぶこともできます。

数学的には、グラフ（頂点、エッジ）を次のように表示できます。

グラフは次の2つのグループに分類できます。

まず、エッジが一方向にしか移動できない場合、グラフをdirectedと呼びます。

たとえば、有向エッジが頂点1と2を接続している場合、頂点1から頂点2にトラバースできますが、反対方向（2から1）は許可されません。したがって、それはに等しくないと言えます。

ただし、エッジが双方向である場合、グラフを無向と呼びます。

たとえば、無向エッジが頂点1と2を接続している場合、頂点1から頂点2へ、および2から1へトラバースできます。そうすれば、それはに等しいと言えます。

グラフ理論では、特定の頂点から始まり、同じ頂点で終わるパスはサイクルと呼ばれます。

循環検出は、コンピュータサイエンスの主要な研究分野です。無向グラフでサイクルを検出する複雑さはです。

以下の例では、ノード3-4-5-6-3がサイクルになることがわかります。

次に、無向グラフでサイクルを検出する方法を学びましょう。具体的には、DFSを使用して実行しましょう。

簡単に言うと、DFSは頂点をスタックに配置します。いくつかの頂点から始めて、それをスタックにプッシュします。それで：

ここで、サイクルを検出するために、DFSのロジックを少し調整できます。次のような訪問済みネイバーがある場合：

その後、サイクルがあります。

これを擬似コードに入れると、次のようになります。

そして今、これを使用して、を呼び出すことにより、無向グラフのサイクルを検出できます。

このクイックチュートリアルでは、深さ優先探索に基づいて、無向グラフでサイクルを検出する方法について説明しました。