データ構造における加重グラフ（重み付きグラフ）の表現方法
グラフは、その性質によっていくつかの種類に分類されます。代表的な分類として、有向グラフと無向グラフ、さらに重み付きグラフと重みなしグラフがあります。本記事では、重み付きグラフをコンピュータのメモリ上でどのように表現・格納するのかを解説します。
例として、次のような重み付きグラフを考えてみましょう。
隣接行列（Adjacency Matrix）による表現
隣接行列の形式で重み付きグラフを格納する場合、この行列はコスト行列とも呼ばれます。各セル M[i, j] には、頂点 i から頂点 j へ向かう辺の重み（コスト）が格納されます。
- 辺が存在しない場合： 値は無限大（∞）となります
- 同じ頂点同士（対角成分）： 値は 0 となります
先ほどのグラフを隣接行列で表すと、以下のようになります。
| 0 | ∞ | 6 | 3 | ∞ |
| 3 | 0 | ∞ | ∞ | ∞ |
| ∞ | ∞ | 0 | 2 | ∞ |
| ∞ | 1 | 1 | 0 | ∞ |
| ∞ | 4 | ∞ | 2 | 0 |
この方式のメリットは、任意の2頂点間の辺の有無や重みを O(1) の計算量で直接参照できる点です。一方で、頂点数の2乗に比例したメモリが必要になるため、辺の数が少ない疎なグラフでは無駄な領域が多くなるというデメリットもあります。
隣接リスト（Adjacency List）による表現
隣接リストでは、各頂点ごとに接続情報のリストを作成し、リスト内の各要素は次の2つの値を持ちます。
- 1つ目： 接続先（行き先）のノード
- 2つ目： その2つのノード間の辺の重み
具体的な表現方法は、以下の図のようになります。
隣接リストは、実際に存在する辺だけを格納するため、疎なグラフにおいてメモリ効率に優れています。このように、グラフの密度や用途に応じて、隣接行列と隣接リストを使い分けることが重要です。
-
ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説
はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ
-
グラフ構造の隣接リスト（Adjacency List）とは？基本概念と実装方法を解説
グラフは代表的な非線形データ構造の一つです。頂点（ノード）でデータを表し、その頂点同士の関係を辺（エッジ）で表現します。グラフGは「頂点の集合V」と「辺の集合E」という2つの要素から構成され、G(V,E)という形式で表記されます。まずは具体例を見てみましょう。このグラフには5つの頂点と5つの辺が存在します。すべての辺には向きが定義されています。例として、頂点BとDを結ぶ辺に注目すると、始点はB、終点はDとなります。そのため、BからDへは移動できますが、逆にDからBへ移動することはできません。グラフは非線形であり、一定の規則性を持たない構造です。そのため、メモリ上でグラフを扱うには、目的に応じた