有向グラフの 2 つの頂点間にパスがあるかどうかを確認します

コンピュータ サイエンスとグラフ理論では、現実のさまざまなモデル シナリオに対するソリューションは有向グラフに大きく依存しています。これらの特殊なグラフは、他の頂点を指す有向エッジによって接続された頂点で構成されます。指定された 2 つの点の間にパスが存在するかどうかを判断することは、有向グラフを使用する典型的な難しい問題です。この記事では、理解を容易にするために各プロセスに必要な構文を含め、C を使用してこのジレンマを解決するさまざまな方法を検討します。さらに、各メソッドを説明するアルゴリズムを詳しく説明し、2 つの実行可能なコード例を示します。

＃＃＃文法＃＃＃

具体的な詳細に入る前に、ここでの方法論を支える言語構造を理解することが重要です。したがって、コード例に進む前に、まずこの構文を確認しましょう。

リーリー ＃＃＃アルゴリズム＃＃＃

有向グラフ内の 2 つの頂点間のパスを見つけることは、さまざまな手法を使用して解決できます。この記事では、広く使用されている 2 つの方法に焦点を当てます -

方法 1: 深さ優先検索 (DFS)

訪問済みの配列を作成して、トラバーサル中に訪問した頂点を追跡します。

• 訪問した配列のすべての要素を false に初期化します。

• startVertex を訪問済みとしてマークします。

• 開始頂点と終了頂点が同じ場合は、パスが存在することを示す true を返します。

• 現在の頂点の隣接する頂点ごとに、その隣接する頂点を新しい開始頂点として使用し、isPathExists 関数を再帰的に呼び出します。

• 再帰呼び出しが true を返す場合、true を返します。

• 再帰呼び出しが true を返さない場合は、false を返します。

• 方法 2: 幅優先検索 (BFS)

訪問済みの配列を作成して、トラバーサル中に訪問した頂点を追跡します。

• 訪問した配列のすべての要素を false に初期化します。

• 保留中の頂点を保存するキューを作成します。

• startVertex をキューに追加し、訪問済みとしてマークします。

• キューが空でない場合は、次の操作を実行します:

• キューから頂点をデキューします。

• デキューされた頂点が endVertex と同じ場合は、パスが存在することを示す true を返します。

• デキューされた頂点に隣接する各頂点について、訪問されていない場合は、それをキューに入れ、訪問済みとしてマークします。

• キューが空になり、パスが見つからない場合は false を返します。

• 例 1: 深さ優先検索 (DFS) 方法

  リーリー ＃＃＃出力＃＃＃ リーリー
コードは、isPathExists という関数を定義することから始まります。この関数は、startVertex、endVertex、および隣接リストで表されるグラフをパラメーターとして受け取ります。これは、訪問された頂点を追跡する Visited と呼ばれるブール ベクトルを初期化します。この関数を実行すると、まず startVertex と endVertex を比較して同じかどうかを確認します。

このコンテキストでこれらの頂点が完全に一致すると、関数はすぐに true を返します。

これに当てはまらず、それらが互いに異なる場合は、それらの間の隣接性をチェックしてそれらの間にパスが存在するかどうかを判断する別のアクションが実行されます。

このプロセスには、開始頂点の隣接する頂点を繰り返し反復することが含まれます。各反復では、新しく検索された頂点を新しい開始点として使用し、「isPathExists」を再帰的に呼び出すことで利用可能なパスの検索を続けます。このサイクルは、可能なパスがすべてなくなるか、成功したパスが見つかるまで繰り返されます。

これらの繰り返される呼び出しのいずれかが、開始ノードと終了ノードを接続する潜在的なエッジを検出した場合、このフィルタリングの出力は、これら 2 つのノード間に使用可能な相互接続が実際に存在することを意味します。したがって、すぐに True が返されます。

そうしないと、アルゴリズムに設定された複雑さによって利用可能なルートがなくなると、フェールセーフ ループ アクションが開始されます。このような結果が発生した場合は、ノード間の接続が失敗したことを示して False を返します。

例 2: 幅優先検索 (BFS) 方法

リーリー ＃＃＃出力＃＃＃ リーリー

このコードは、startVertex、endVertex、および隣接リストで表されるグラフをパラメータとして受け取る isPathExists 関数を定義します。これは、訪問された頂点を追跡するために Visited と呼ばれるブール ベクトルを初期化し、保留中の頂点を格納するために verticesQueue と呼ばれるキューを初期化します。

この関数は、startVertex をキューに入れ、訪問済みとしてマークすることで開始されます。私たちのアルゴリズムの動作は、処理キュー構造内に項目がある限り継続する反復ループに入ることから始まります。この構造化された反復が進むにつれて、サイクルごとに 2 つのチェックが実行されます: まず、現在の反復のデキューされた頂点が、前の実行で指定されたターゲット エンドポイントと一致するかどうかを確認します。2 つが正常に一致した場合は、「true」を返し、それ以外の場合は、次のステップに進みます。近くの辺境のポイントを探索します。この探索プロセス中、隣接する未探索の頂点はすべて「訪問済み」としてマークされてから、より深い反復と endVertex と一致するかどうかのテストのためにキューに入れられます。

すべての探索と検証が成功した後、キューに何も追加されない場合、関数は false を返します。

＃＃＃結論は＃＃＃

コンピュータ サイエンスの発展において、有向グラフをナビゲートする複雑さが根本的な問題を引き起こす可能性があります。これらの課題を軽減するために、私たちの目標の 1 つは、C で実装された 2 つの一般的なアプローチを調査することです。深さ優先検索 (DFS) と幅優先検索 (BFS) はこれらの技術の最前線にあり、各アルゴリズムを示す段階的な手順と実用的なコード例を提供します。これらの方法を習得すると、複数の設定（ネットワークのルーティングやソーシャル接続フレームワークの分析など）で経路探索の障害に対処するときに新たな可能性が解き放たれ、機能強化の開発段階での貴重な出発点として機能します。

以上が有向グラフの 2 つの頂点間にパスがあるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。