1. 概要

グラフ理論では、開始ノードから到達可能なノードを判別することが不可欠です。 この記事では、グラフの2つのノードが接続されているかどうかを判断する問題について説明します。

最初に、有向グラフと無向グラフの両方の問題について説明します。 次に、問題を解決できる2つのアプローチを示します。

最後に、両方のアプローチの主な違いをリストした比較を示し、それぞれをいつ使用するかを説明します。

2. 問題の定義

この問題では、ノードとエッジのグラフが表示されます。 タスクは、複数のクエリに答えることです。 各クエリでは、 2つのノードとが与えられ、ノードから開始してノードに到達できるかどうかを判断するように求められます。

エッジの方向における有向グラフと無向グラフの違いにより、これらのグラフごとに問題を異なる方法で調べる必要があります。

そこで、各グラフタイプの観点から問題を説明します。

2.1. 有向グラフ

グラフの例を使用して、アイデアをよりよく説明しましょう。

たとえば、開始ノードがノード1で、終了ノードがノード3であるとします。 この場合、パス{1、2、3}をたどることでノード1から3に移動できるため、答えはです。

次に、逆の場合を考えてみましょう。 開始ノードがノード3で、終了ノードがノード1の場合、ノード3からノード1に直接エッジがあるため、答えはまだです。

ただし、これが常に当てはまるとは限りません。 ノード1であり、4であるとします。 この場合、答えはノード1からノード4に移動できるためです。 一方、がノード4でがノード1である逆の場合は、ノード4からノード1に移動できないため、答えが得られます。

さらに、ノード1と8の両方のケースで、に等しい答えがあります。 その理由は、ノード1からノード8に移動することも、ノード8からノード1に移動することもできないためです。

この例から、開始ノードと終了ノードの順序が重要であると結論付けることができます。 したがって、ノードとクエリを切り替えることはできず、同じ回答が得られると期待できます。

2.2. 無向グラフ

無向グラフでは、状況が異なります。 有向グラフで提供されているものと同じ例を取り上げますが、すべてのエッジを無向にします。 グラフがどのように見えるか見てみましょう。

セクション2.1で提供されている同様の例を取り上げます。 がノード1でノード3であるとすると、答えはノード1からノード3に移動できるためです。

同様に、ノード3からノード1に移動することもできます。 したがって、がノード3で、がノード1の場合、答えは引き続きです。

ただし、ノード1をノード8とすると、ノード1からノード8に到達できないためです。 同様に、がノード8でノード1の場合、答えはまだです。

その結果、無向グラフに一方のノードからもう一方のノードへのパスが含まれている場合、それは確かに2番目のノードから最初のへのパスが含まれていることを意味すると結論付けることができます。 その理由は、すべてのエッジが無向であり、パスを両方向にトラバースできるためです。

問題を十分に定義したので、解決策の説明に取り掛かることができます。 簡単にするために、グラフは隣接リストに格納されていると仮定します。

3. 素朴なアプローチ

素朴なアプローチは、各クエリの開始ノードからDFSトラバーサルを実行することに基づいています。 終了ノードに到達できれば、答えはです。 それ以外の場合、答えはです。 素朴なアプローチの実装を見てみましょう。

最初に、配列を値で初期化し、ノードから開始してDFS関数を呼び出します。 また、グラフ、終了ノード、および配列を渡します。

DFS関数内では、最初に終了ノードに到達したかどうかを確認します。 もしそうなら、私たちはを返します。

まだ終了ノードに到達していない場合は、現在のノードに以前にアクセスしたことがあるかどうかを確認します。 以前にアクセスしたことがある場合は、を返します。これは、現在のノードが以前にアクセスしたことを示します。 したがって、に到達できた場合は、以前に戻っていたはずです。

それ以外の場合は、現在のノードを訪問済みとしてマークし、隣接するノードを反復処理します。 ネイバーごとに、再帰的なDFS呼び出しを実行します。 再帰的なDFS呼び出しを実行するとき、現在のノードとしてネイバーを渡します。 これは、ノードから開始して検索を続行することを意味します。

この呼び出しが戻った場合、他のネイバーをチェックせずに、すぐに戻ります。

ただし、すべてのネイバーからDFS操作を実行する場合があり、いずれもを返しません。 この場合も戻り、現在のノードから到達できなかったことを示します。

単純なアプローチの複雑さは、クエリごとです。ここで、はノードの数であり、はグラフ内のエッジの数です。 複雑さは、グラフに対して深さ優先探索を実行することと同じです。

4. 各ノードのコンポーネントを見つける

まず、このアプローチの一般的な考え方を説明しましょう。 次に、実装について説明します。

4.1. 一般的なアイデア

無向グラフを扱うときは、より良いアプローチを考え出すことができます。 主な考え方は、無向グラフでは、から開始して到達できる場合、から開始して到達できるということです。 その理由は、すべてのエッジを両方向に渡すことができるためです。

したがって、最初から到達できない場合は、それぞれが異なるコンポーネントにある場合のみです。 ただし、両方のノードが同じコンポーネント内にある場合は、互いに到達できます。

セクション2.2で取ったグラフの例を2つのコンポーネントに分けてみましょう。

接続された各コンポーネントを異なる色で着色しました。 赤いコンポーネントのすべてのノードは、相互に到達可能です。 青いコンポーネントのノードにも同じことが当てはまります。

その結果、次の2つのステップに基づいてアプローチを構築できます。

  1. 質問に答える前に、はDFS操作を実行して、グラフをコンポーネントに分割します。 このステップでは、コンポーネントごとに異なるコンポーネント識別子を割り当てます。 また、各ノードのを保存します。
  2. クエリごとに、ノードとが同じコンポーネント内にあるかどうかを確認します。 その場合は、を返します。 それ以外の場合は、を返します。

これで、このアプローチの実装に飛び込むことができます。

4.2. 事前計算

事前計算ステップの実装を見てみましょう。

まず、配列を値で、配列を-1で、変数をゼロで初期化します。

次に、グラフ内のすべてのノードを反復処理します。 各ノードについて、これまでにアクセスされていない場合は、このノードからDFS操作を開始します。 その前に、変数を1つ増やして、探索する新しいコンポーネントを示します。 また、DFS関数にいくつかのパラメーターを渡します。

  1. グラフ。
  2. コンポーネントの探索を開始するノード。
  3. これまでにアクセスしたノードを格納する配列。
  4. これまでに調査した各ノードのコンポーネント識別子を格納する配列。
  5. 現在探索されているコンポーネントの識別子を含む変数。

最後に、配列を返します。

DFS関数の開始時に、このノードが以前にアクセスされたことがあるかどうかを確認します。 もしそうなら、私たちは単に戻って、現在のノードを探索しません。 それ以外の場合は、現在のノードを訪問済みとしてマークします。

その後、配列内の現在のノードの現在のコンポーネントIDを格納します。

最後に、現在のノードのすべてのネイバーを反復処理し、これらの各ネイバーから開始して再帰的なDFS呼び出しを実行します。

事前計算ステップの複雑さはです。ここで、はノードの数、はグラフ内のエッジの数です。 このステップは、クエリに回答する前に1回だけ実行されることに注意してください。

4.3. 質問に答える

事前計算ステップを実行した後、各クエリに効率的に答えることができます。 各クエリに答える実装を見てみましょう。

実装はかなり簡単です。 ノードのコンポーネント識別子がノードのコンポーネント識別子と等しいかどうかを確認するだけです。 もしそうなら、私たちは戻ります。 それ以外の場合は、を返します。

このアプローチの複雑さは、配列内に格納されている値のみをチェックしているためです。

5. 比較

両方のアプローチの比較をリストした次の表を考えてみましょう。

無向グラフを検討する場合、連結成分に基づくアプローチの方が複雑です。 その理由は、事前計算ステップを1回だけ実行するためです。 その後、各クエリはで効率的に回答できます。

ただし、有向グラフの連結成分に基づくアプローチを使用することはできません。 したがって、有向グラフの場合は、単純なアプローチを使用する必要があります。

6. 結論

このチュートリアルでは、グラフ内の2つのノードが接続されているかどうかを確認する問題を示しました。

最初に、有向グラフと無向グラフの場合の問題について説明しました。

その後、問題を解決できる2つのアプローチを紹介しました。

最後に、両方のアプローチの主な違いを示し、各アプローチをいつ使用するかを示す比較表をリストしました。