隣接リストとグラフの行列表現
サラ・チェン
見た目は違っても、みんな グラフの種類 と同様の方法で表すことができます。 一般に、グラフ表現には XNUMX つのタイプがあります。
- 隣接行列
- 隣接リスト
隣接リスト
隣接リストはリンク リストで構成されます。 各頂点は配列インデックスとみなされ、各要素はリンクされたリストを表します。 これらのリンクされたリストには、インデックス頂点を持つエッジを持つ頂点が含まれます。
隣接リストの例を次に示します。
グラフに V 個の頂点と E 個のエッジが含まれているとします。
一般的に、空間計算量は O(V + E).
最悪の場合の空間複雑度は O(V2) 指定されたグラフが完全なグラフの場合
隣接行列
隣接行列は 2D 配列で構成されます。 V 個の頂点を持つグラフ、行列のサイズは次のようになります。 VxV.
言って、 matrix[i][j] = 5。 これは、ノード i と j の間に重みが 5 のエッジがあることを意味します。
次のグラフとその隣接行列を見てみましょう。
作成しました 2D配列 次の手順を使用します。
ステップ1） 頂点 A には B と直接エッジがあり、重みは 5 です。したがって、行 A と列 B のセルは 5 で埋められます。行 A の残りのセルは XNUMX で埋められます。
ステップ2） 頂点 B には C との直接エッジがあり、重みは 4 です。したがって、行 B と列 C のセルは 4 で埋められます。B にはどのエッジにも出力されないため、行 B の残りのセルはゼロで埋められます。他のノード。
ステップ3） 頂点 C には、他の頂点との直接のエッジがありません。 したがって、行 C はゼロで埋められます。
ステップ4） 頂点 D には、A および C との有向エッジがあります。
- ここで、行 D と列 A のセルの値は 7 になります。行 D と列 C のセルの値は 2 になります。
- 行 D の残りのセルはゼロで埋められます。
ステップ5） 頂点 E には B および D との有向エッジがあります。行 E および列 B のセルの値は 6 になります。行 E および列 D のセルの値は 3 になります。行 D の残りのセルは次のようになります。ゼロで埋められています。
注意すべき点がいくつかあります。
- 隣接行列の主対角が 0 の場合、グラフには自己ループがありません。
- インデックス (a,b) と (b,a) が同じ値を持たない場合、グラフは有向グラフです。 それ以外の場合、グラフは有向グラフです。
- セルの値が 1 より大きい場合、グラフは加重グラフになります。
隣接行列には正方形のスペースが必要なので、問題があります。 ここでは、接続されていないエッジを保存しています。 これらのエッジはメモリ内のスペースを割り当てます。
たとえば、100 個のノードを持つグラフがある場合、それを保存するには 10 個のセルが必要です。 RAMグラフの辺が少ない場合、このような大きなメモリを割り当てるのは無駄になる可能性があります。したがって、隣接行列を使用した空間計算量は、 O(N2)ここで、N はグラフ内のノードの数を意味します。
