グラフの表現

6.1 隣接行列：動作原理、メリットとデメリット。

隣接行列は、グラフをサイズn x nの正方行列で表す方法で、nはグラフの頂点の数です。行列の要素は頂点間の辺の有無を示します：

• もし頂点iとjの間に辺があるならば、要素A[i][j] = 1（重み付きグラフの場合は辺の重み）です。
• 辺がない場合は、A[i][j] = 0です。

例:

頂点A、B、Cと辺(A, B)、(B, C)、(C, A)を持つグラフの隣接行列は次のようになります：

すべての頂点がすべての頂点と接続されていた場合、隣接行列は次のようになります：

メリット:

• 簡単さ：理解しやすく、実装が簡単です。
• 高速アクセス：2つの頂点間の辺の有無の確認はO(1)で行われます。
• 密なグラフに適している：辺が多いグラフに効果的です。

デメリット:

• 高いメモリ消費：グラフが少ない辺しか持たない場合（スパースグラフ）でもO(n^2)のメモリが必要です。
• スパースグラフには非効率的：頂点が多くて辺が少ないと、行列の大部分がゼロになり、メモリの使用が非効率的になります。

6.2 隣接リスト：動作原理、メリットとデメリット。

隣接リストは、グラフをリストの配列として表す方法です。配列の各要素はグラフの頂点に対応し、その頂点に隣接するすべての頂点のリストを含みます。

例:

頂点A、B、Cと辺(A, B)、(B, C)、(C, A)を持つグラフの隣接リストは次のようになります：

すべての頂点がすべての頂点と接続されていた場合、隣接リストは次のようになります：

メリット:

• メモリの効率的な使用：O(V + E)のメモリが必要で、これはスパースグラフに適しています。
• 容易な遍歴：グラフの遍歴（例えば広さ優先検索や深さ優先検索）を行うのに便利です。

デメリット:

• アクセスが複雑：2つの頂点間の辺の有無の確認にはO(k)時間がかかり、kは頂点の隣接者の数です。
• 構造がわかりにくい：隣接行列と比べて、実装や理解が難しいです。

6.3 グラフの表現方法の比較。

それでは、グラフを表現するさまざまな方法を比較しましょう。

1. 隣接行列:

• 簡単さ：理解しやすく、実装が容易です。
• メモリ：O(n^2)のメモリが必要なので、スパースグラフには非効率的です。
• 高速アクセス：辺の有無の確認はO(1)で行われます。
• 適している：辺が多い密なグラフに適しています。

2. 隣接リスト:

• 簡単さ：隣接行列よりわかりにくいですが、理解可能です。
• メモリ：O(V + E)のメモリが必要で、スパースグラフに効率的です。
• 高速アクセス：辺の有無の確認にはO(k)時間がかかり、kは頂点の隣接者の数です。
• 適している：辺が少ないスパースグラフに適しています。

比較:

隣接行列は、ほとんどの頂点が辺で接続されている密なグラフに適しており、辺情報への高速アクセスを提供し、実装が簡単です。

隣接リストは、可能な頂点ペアの数よりも辺の数がはるかに少ないスパースグラフに適しており、メモリを効率的に使用し、グラフの遍歴操作に便利です。