1. 概要

この記事では、グラフ内の2つの任意の頂点間のすべての単純なパスを見つける問題について説明します。

問題の定義から始めましょう。 次に、この問題を解決するアルゴリズムについて説明します。

最後に、いくつかの特殊なケースについて説明します。 有向グラフに焦点を当て、アルゴリズムが無向グラフでも同じであることを確認します。

2. 意味

まず、単純なパスの定義を思い出してみましょう。 有向グラフがあるとします。ここで、は頂点のセットであり、はエッジのセットです。 2つの頂点間の単純なパスであり、次の条件を満たす一連の頂点です。

  • 頂点のセットに属するすべてのノード
  • ,
  • 2つの連続する頂点ごとに、ここで、はエッジのセットに属するエッジがあります。
  • シーケンス内に複数回出現する頂点はありません。 つまり、単純なパスにはサイクルがありません

この問題により、グラフと2つのノード、、が得られ、2つのノードとの間のすべての可能な単純なパスを見つけるように求められます。

グラフは、有向または無向のいずれかになります。 有向グラフから始めて、次に、無向グラフに関連するいくつかの特殊なケースを示します。

たとえば、グラフについて考えてみましょう。

 

ご覧のとおり、頂点1と4の間には5つの単純なパスがあります。

パスにはサイクルが含まれているため、パスは単純ではないことに注意してください。頂点4はシーケンスに2回表示されます。

3. アルゴリズム

3.1. 理論的アイデア

基本的な考え方は、深さ優先探索（DFS）アルゴリズムとバックトラッキングを使用して、考えられるすべてのソリューションを生成することです。

最初に、ソース頂点からDFS操作を開始します。 次に、すべての隣人を調べようとします。 ネイバーごとに、すべてのネイバーを通過しようとします。

うまくいけば、目的の頂点に到達できるようになります。 これが発生すると、ウォークパスを有効な単純パスのセットに追加します。 次に、他のパスの検索に戻ります。

サイクルを回避するには、単純なパスで頂点が複数回アクセスされないようにする必要があります。 そのために、パスに初めて入力したときに、すべての頂点を訪問済みとしてマークします。 したがって、すでにアクセスした頂点にアクセスしようとすると、すぐに戻ります。

いくつかの頂点を処理した後、現在のパスからそれを削除する必要があるため、戻る前に未訪問としてマークします。 このステップの理由は、同じノードが複数の異なるパスの一部になる可能性があるためです。 ただし、同じパスに複数回含めることはできません。

3.2. 実装

今説明したアイデアの実装を見てみましょう。

まず、配列を値で初期化します。これは、ノードがまだアクセスされていないことを示します。 また、リストとリストを空に初期化します。 リストには現在のパスが保存されますが、リストには結果のパスが保存されます。

その後、DFS関数を呼び出して、結果の単純なパスを返します。 DFS関数の実装を確認してみましょう。

まず、頂点にアクセスしたかどうかを確認します。 もしそうなら、私たちはサイクルに達したので戻ってきます。 それ以外の場合は、関数を使用して現在のパスの最後に追加し、ノードを訪問済みとしてマークします。

次に、頂点が宛先頂点と等しいかどうかを確認します。 もしそうなら、私たちは完全に有効な単純なパスに到達しました。 したがって、このパスを結果リストに追加して戻ります。

ただし、宛先ノードにまだ到達していない場合は、現在の頂点の各隣接ノードに対して再帰的にパスを継続しようとします。

最後に、リストの最後に格納されている値を削除する関数を使用して、現在のパスから現在のノードを削除します（現在のノードをリストの最後に追加したことを思い出してください）。 また、ノードを未訪問としてマークして、他の単純なパスで繰り返すことができるようにします。

3.3. 複雑

グラフが完全である、つまり頂点のすべてのペアの間にエッジがあるという最悪のシナリオを検討します。 この場合、問題はそれらを訪問する頂点の順列を見つける可能性が高いことがわかります。

頂点の順列ごとに、対応するパスがあります。 したがって、の複雑さはです。ここで、は頂点の数であり、は頂点の数の階乗です。

もちろん、この複雑さは非常に大きいですが、バックトラッキングアプローチを使用しているため、これは驚くべきことではありません。

4. 無向グラフ

以前のアルゴリズムは、有向グラフと無向グラフの両方で完全に正常に機能します。 その理由は、各無向エッジを2つの有向エッジとに置き換えることで、任意の無向グラフを同等の有向グラフに変換できるためです。

ただし、無向グラフでは、グラフがツリーを形成する特殊なケースがあります。 このケースについては個別に説明します。

5. 木

ツリーは、サイクルのない無向の連結グラフであることに注意してください。

この場合、ツリー内のノードのペア間には1つの単純なパスがあります。 具体的には、このパスは、2つのノードの最も低い共通祖先（LCA）を通過します。 つまり、パスはノードから始まり、との間のLCAまで進み続け、次に。に進みます。

たとえば、以下に示すツリーを見てみましょう。

 

このツリーでは、ノード7と8の間の単純なパスは、ノード3であるLCAを通過します。 同様に、ノード4と9の間のパスは、ノード1であるLCAを通過します。

6. サイクルのない切断された無向グラフ

一般的なケースでは、サイクルのない無向グラフは常に接続されているとは限りません。 グラフが切断されている場合、それはフォレストと呼ばれます。 フォレストはコンポーネントのセットであり、各コンポーネントはそれ自体でツリーを形成します。

森林を扱う場合、2つのシナリオが考えられます。 1つは、両方のノードが同じコンポーネントにある場合があります。その場合、単一の単純なパスがあります。 その理由は、両方のノードが同じツリー内にあるためです。

一方、各ノードが異なるツリーにある場合、それらの間に単純なパスはありません。 これは、各ノードが異なる切断されたコンポーネントにあるためです。

たとえば、以下のフォレストを見てください。

このグラフでは、ノード2と3の間に単純なパスがあります。これは、両方がノード{}を含む同じツリーにあるためです。 ただし、ノード5と8は異なるツリーに存在するため、ノード5と8の間に単純なパスはありません。

7. 結論

このチュートリアルでは、グラフ内の2つのノード間のすべての単純なパスを見つける問題について説明しました。

最初に、例から始めて、その解決策を説明しました。 その後、アルゴリズムとその理論的アイデアおよび実装を紹介しました。

最後に、無向グラフに関連するいくつかの特殊なケースについて説明しました。