グラフのデータ構造とは何ですか?
あ グラフ は、頂点とエッジで構成される非線形データ構造です。頂点はノードと呼ばれることもあり、エッジはグラフ内の任意の 2 つのノードを接続する線または円弧です。より正式には、グラフは一連の頂点で構成されます( で ) とエッジのセット( そして ）。グラフは次のように表されます。 G(V,E) 。
グラフの表現
グラフを表現する最も一般的な 2 つの方法を次に示します。
- 隣接行列
- 隣接リスト
隣接行列
隣接行列は、グラフをブール値 (0 と 1) の行列として表現する方法です。
あると仮定しましょう n グラフ内の頂点 そこで、2D 行列を作成します adjMat[n][n] 次元 n x n を持ちます。
- 頂点からのエッジがある場合 私 に j 、 マーク adjMat[i][j] として 1 。
- 頂点からのエッジがない場合 私 に j 、 マーク adjMat[i][j] として 0 。
無向グラフから隣接行列への表現:
以下の図は、無向グラフを示しています。最初に、マトリックス全体が次のように初期化されます。 0 。ソースから宛先までのエッジがある場合は、 1 どちらの場合も( adjMat[目的地] そして 調整マット [ 行き先]） どちらの方向にも進むことができるからです。
無向グラフから隣接行列へ
有向グラフから隣接行列への表現:
以下の図は有向グラフを示しています。最初に、マトリックス全体が次のように初期化されます。 0 。ソースから宛先までのエッジがある場合は、 1 その特定の adjMat[目的地] 。
隣接行列への有向グラフ
隣接リスト
リストの配列は、2 つの頂点間のエッジを格納するために使用されます。配列のサイズは次の数に等しい 頂点 (つまり、n) 。この配列内の各インデックスは、グラフ内の特定の頂点を表します。配列のインデックス i のエントリには、頂点に隣接する頂点を含むリンク リストが含まれます。 私 。
あると仮定しましょう n グラフ内の頂点を作成します。 リストの配列 サイズの n として adjList[n]。
- adjList[0] には、頂点に接続 (隣接) されているすべてのノードが含まれます。 0 。
- adjList[1] には、頂点に接続 (隣接) されているすべてのノードが含まれます。 1 等々。
隣接リストに対する無向グラフの表現:
以下の無向グラフには 3 つの頂点があります。したがって、リストの配列はサイズ 3 で作成され、各インデックスは頂点を表します。ここで、頂点 0 には 2 つの隣接頂点 (つまり、1 と 2) があります。したがって、配列のインデックス 0 に頂点 1 と 2 を挿入します。同様に、頂点 1 には 2 つの隣接点 (つまり 2 と 0) があるため、配列のインデックス 1 に頂点 2 と 0 を挿入します。同様に、頂点 2 については、その近傍をリストの配列に挿入します。
無向グラフから隣接関係リストへ
隣接リストに対する有向グラフの表現:
以下の有向グラフには 3 つの頂点があります。したがって、リストの配列はサイズ 3 で作成され、各インデックスは頂点を表します。現在、頂点 0 には隣接する頂点がありません。頂点 1 には 2 つの隣接点 (つまり、0 と 2) があるため、配列のインデックス 1 に頂点 0 と 2 を挿入します。同様に、頂点 2 については、その近傍をリストの配列に挿入します。
隣接リストへの有向グラフ