アークのセットを隣接マトリックスと隣接テーブルとして表す方法は？

図の表現：隣接するマトリックスと隣接テーブルの変換へのアーク

この記事では、指示されたアークのセットをグラフの2つの一般的な表現に変換する方法を示しています：隣接マトリックスと隣接テーブル。次のアークセットを例として使用します：⟨V0、V1、V1、V1、V1、V3、V2、V3。この一連のアークは、4つの頂点（V0、V1、V2、V3）を持つ指向グラフを記述します。

まず、これらのアークを解釈しましょう。V0からV1を指す方向のエッジで示された⟨V0、V1。 v1の頂点で示されるv1、v1の頂点の自己ループで示されています。 V1からV3への指示されたエッジで示されるv3、V3。 v2からV3への指示されたエッジで示されるv3、V3。

隣接するマトリックス表現：

隣接マトリックスは、2次元配列を使用してグラフを表します。配列の行と列は、それぞれグラフの頂点に対応しています。頂点Iから頂点Jまでのエッジがある場合、マトリックス要素A _IJは1です。そうでなければ0です。重み付きグラフの場合、 _IJはエッジの重量を保存できます。

指定されたアークセットに基づいて、4x4隣接マトリックスを構築できます。

<code> v0 v1 v2 v3 v0 0 1 0 0 v1 0 1 0 1 v2 0 0 0 1 v3 0 0 0 0</code>

隣接するテーブル表現：

隣接するテーブルは、特にスパースグラフの場合、よりスペース節約グラフ表現方法です。配列の各要素が頂点に対応し、その頂点に隣接する頂点を格納するリンクリストを指す配列を使用します。

特定のアークのセットに基づいて、対応する隣接テーブルは次のとおりです。

 <code>v0: v1 v1: v1, v3 v2: v3 v3:</code>

これは、V0がV1に接続されていることを意味します。 V1はそれ自体（自己ループ）およびV3に接続されています。 V2はV3に接続されています。 V3には、時代遅れのエッジがありません。

概要：この記事では、アークのセットを隣接するマトリックスと隣接テーブルに変換する方法を示しています。これらの2つの表現方法には、独自の利点と短所があります。選択される方法は、特定のアプリケーションシナリオとグラフの特性（たとえば、グラフのまばら性）に依存します。

以上がアークのセットを隣接マトリックスと隣接テーブルとして表す方法は？の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。