グラフとその表現

グラフは非線形のデータ構造です。これは、ノードを使用したデータと、エッジを使用したそれらの関係を表します。グラフGには2つのセクションがあります。頂点とエッジ。頂点はセットVを使用して表され、エッジはセットEとして表されます。したがって、グラフ表記はG（V、E）です。アイデアを得るための1つの例を見てみましょう。

このグラフには、5つの頂点と5つのエッジがあります。エッジが方向付けられます。例として、頂点BとDを接続するエッジを選択した場合、ソース頂点はBで、デスティネーションはDです。したがって、BをDに移動することはできますが、DからBに移動することはできません。

グラフは非線形であり、規則的な構造はありません。メモリ内のグラフを表すために、いくつかの異なるスタイルがあります。これらのスタイルは-

• 隣接行列表現
• エッジリストの表現
• 隣接リストの表現

隣接行列の表現

隣接行列を使用してグラフを表すことができます。与えられた行列は隣接行列です。これはバイナリの正方行列であり、i番目の行からj番目の列まで、エッジがある場合、その場所は1としてマークされます。隣接行列を使用して無向グラフを表現しようとすると、行列は対称になります。

エッジリストの表現

グラフは、1次元配列を使用して表すこともできます。これはエッジリストと呼ばれます。この表現には5つのエッジがあり、各エッジに対して最初の要素がソースで、2番目の要素が宛先です。無向グラフ表現の場合、エッジリストの要素数は2倍になります。

隣接リストの表現

これは別のタイプのグラフ表現です。これは隣接リストと呼ばれます。この表現は、リンクリストに基づいています。このアプローチでは、各ノードは、その頂点に直接接続されているノードのリストを保持しています。リストの最後で、各ノードはnull値に接続され、そのリストの最後のノードであることを示します。