頂点 X と Y が無向グラフの同じ接続コンポーネント内にあるかどうかをクエリします

グラフ理論は、連結成分の研究をカバーします。連結成分は、頂点のすべてのペアがパスによってリンクされ、他の頂点がそれに接続されていない無向グラフの部分グラフです。

この記事では、C/C プログラミング言語を使用して、2 つの頂点 X と Y が無向グラフ内の同じ連結成分に属しているかどうかを判断する方法について詳しく説明します。この問題を解決する少なくとも 2 つの異なる方法を明らかにする前に、このメソッドの構文と理論的根拠を明確にします。さらに、各メソッドの具体的なコード例とそれに対応する結果も提供します。

＃＃＃文法＃＃＃

提供されたコード スニペットでは、グラフィカルな表現のために C で 3 つの関数を宣言しています。 isConnected 関数は 2 つの頂点 X と Y を受け取り、それらが同じ接続コンポーネントに属しているかどうかを示すブール値を返します。 addEdge 関数は 2 つの頂点 X と Y を受け取り、グラフ内でそれらの間に接続を作成します。 InitializeGraph 関数は、整数値 n を入力として受け取り、n 個の頂点を持つグラフを設定します。これらの関数は、深さ優先検索や幅優先検索などのさまざまなグラフ アルゴリズムを使用して実行し、2 つの頂点の接続性を確認し、グラフ内の頂点間の接続を確立できます。

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

ステップ 1

- グラフの初期化関数を使用して、指定した頂点数でグラフを初期化します。

ステップ 2 - addEdge 関数を使用して頂点間にエッジを追加します

ステップ 3 - グラフ トラバーサル メソッドを実装して、頂点に関連するすべての頂点をトラバースし、その頂点を訪問済みとしてマークします。

ステップ 4 - 構築されたグラフ走査方法を使用して、頂点 X と Y の両方が訪問されたかどうかを判断します。

ステップ 5 - 頂点 X と Y の両方にアクセスした場合は true を返し、それ以外の場合は false を返します。

＃＃＃方法＃＃＃

方法 1

- DFS を使用します。これは、グラフを調査するために頂点を繰り返し訪問し、訪問済みとしてマークするグラフ トラバーサル アルゴリズムです。

• 方法 2 - データ構造を使用して、コレクションが異なるサブグループに分割されているかどうかを監視するユニオン検索方法を使用します。無向グラフの接続部分を効果的に識別できます。

• 方法1 このメソッドでは、DFS を使用して頂点 X と Y が同じ連結コンポーネント内にあるかどうかを確認します。頂点 X から開始して、DFS を使用してグラフを横断できます。

例 1

コードは、2 つの頂点 X と Y がグラフ内の同じ連結成分に属しているかどうかを検証するために評価されます。深さ優先検索 (DFS) アルゴリズムを使用してグラフを走査し、頂点の接続性を決定します。グラフは隣接リストを使用して記述されます。隣接リストでは、頂点間のエッジが各頂点の隣接する頂点のリストとして保存されます。このコードは、DFS トラバーサル中に探索された頂点を監視するために、訪問された配列を初期化します。頂点 X で DFS 関数を実行します。DFS プロセス中に頂点 Y が訪問されたことが判明した場合、X と Y の両方が同じ連結コンポーネントの一部であることを意味します。 main 関数は、隣接リストを作成してそれにエッジを追加することによってグラフを設定し、複数のクエリを実行して 2 つの頂点が同じ連結成分内にあることを確認します。

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

方法 2

このアプローチでは、and find メソッドを使用して頂点 X と Y が同じリンク コンポーネント内にあるかどうかを判断するために、まず各頂点を素のセットに割り当てます。その後、エッジ エンドポイントのコレクションをグラフ内のエッジごとに組み合わせることができます。最後に、頂点 X と Y が同じセットのメンバーであるかどうかを判断でき、それらが関連するコンポーネントであることを示します。

例 2

このコードは、2 つの頂点がグラフの同じ接続コンポーネント内にあるかどうかを確認するアルゴリズムを実装および検索します。入力は、頂点数 n、エッジ数 m、エッジ配列 Edges[m][2]、クエリ番号 q およびクエリ配列 Queries[q][2] の形式でハードコーディングされます。 。関数 merge(u, v) は、頂点 u を含むセットと頂点 v を含むセットをマージします。関数 areVerticesInSameComponentUnionFind(X, Y) は、頂点 X と Y が同じ接続コンポーネント内にあるかどうかを、親ノードを見つけて調べ、それらが等しいかどうかをチェックします。それらが等しい場合、頂点は同じ連結コンポーネント内にあります。そうでない場合は、頂点は同じ連結コンポーネント内にありません。クエリ結果がコンソールに出力されます。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

このコードでは、2 つの無向グラフ頂点 X と Y が相互に関連しているかどうかを判断する 2 つの方法を紹介します。 2 番目の戦略では、和集合検索アルゴリズムを使用して素セットを追跡します。一方、最初のアプローチでは深さ優先検索 (DFS) を使用してグラフを横断し、訪問した頂点をマークします。

以上が頂点 X と Y が無向グラフの同じ接続コンポーネント内にあるかどうかをクエリしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。