グラフを保存するためのデータ構造: 既存のデータ構造と XNUMX つの「ほぼ新しい」データ構造のレビュー

こんにちは。

このメモでは、コンピューターサイエンスでグラフを保存するために使用される主なデータ構造をリストすることにしました。また、私にとってどういうわけか「結晶化」したそのような構造をさらにいくつかお話します。

それでは、始めましょう。 しかし、最初からではありません。私たちは皆、グラフが何であるか、そしてそれらが何であるか（有向、無向、重み付き、重みなし、複数のエッジやループの有無にかかわらず）すでに知っていると思います。

じゃ、行こう。 「グラフストレージ」のデータ構造にはどのようなオプションがありますか?

1. 行列データ構造

1.1 隣接行列。 隣接行列は、行と列の見出しがグラフの頂点の数に対応する行列で、その各要素 a(i,j) の値は頂点間のエッジの有無によって決まります。 i と j (無向グラフの場合、そのような行列が対称であることは明らかです。または、すべての値を主対角の上にのみ保存することに同意できます)。 重み付けされていないグラフの場合、a(i,j) は i から j までのエッジの数によって設定できます (そのようなエッジがない場合は、a(i,j)= 0)。重み付けされたグラフの場合は、重みによっても設定できます。前述のエッジの（総重量）。

1.2 発生率マトリックス。 この場合、グラフはテーブルにも保存されます。テーブルでは、原則として、行番号がその頂点の番号に対応し、列番号が事前に番号付けされたエッジに対応します。 頂点とエッジが互いに衝突する場合、対応するセルにゼロ以外の値が書き込まれます (無向グラフの場合、頂点とエッジが衝突する場合は 1 が書き込まれます。有向グラフの場合、エッジが衝突する場合は「1」が書き込まれます)。頂点から「出る」場合は「-1」、頂点に「含まれる」場合は「-1」になります（数字「-1」には「マイナス」記号も「含まれる」ようですので、覚えておくのは簡単です）。 重み付きグラフの場合も、1 と -XNUMX の代わりに、エッジの合計重みを指定できます。

2. 列挙型データ構造

2.1 隣接リスト。 さて、ここではすべてが簡単に見えます。 一般に、グラフの各頂点は、指定された頂点に隣接するすべての頂点の番号を格納する任意の列挙構造 (リスト、ベクトル、配列など) に関連付けることができます。 有向グラフの場合、フィーチャ頂点から「有向」エッジが存在する頂点のみをそのようなリストに追加します。 重み付きグラフの場合、実装はより複雑になります。

2.2 リブのリスト。 非常に一般的なデータ構造です。 Captain Obviousness が言うように、エッジのリストは実際にはグラフのエッジのリストであり、各エッジは開始頂点と終了頂点によって指定されます (無向グラフの場合、順序はここでは重要ではありませんが、統合の場合は次のようにすることができます)たとえば、頂点の増加順の指定や重み付け (重み付けされたグラフのみ) など、さまざまなルールを使用します。

上記のマトリックス リストをさらに詳しく (および図を使用して) 確認できます。たとえば、次のようになります。 ここで.

2.3 隣接配列。 最も一般的な構造ではありません。 その核心は、隣接リストを XNUMX つの列挙構造 (配列、ベクトル) に「詰め込む」形式です。 このような配列の最初の n (グラフの頂点の数に応じた) 要素には、同じ配列の開始インデックスが含まれており、そこから開始して、指定された頂点に隣接するすべての頂点が行に書き込まれます。

ここで（私にとって）最もわかりやすい説明を見つけました。 ejuo.livejournal.com/4518.html

3. 隣接ベクトルと連想隣接配列

これらの行の作成者はプロのプログラマではありませんが、定期的にグラフを扱っており、最も頻繁にエッジのリストを扱っていることが判明しました。 確かに、グラフに複数のループとエッジがあると便利です。 したがって、エッジの古典的なリストの開発において、私はそれらの「発生/分岐/変更/突然変異」、つまり隣接ベクトルと連想隣接配列に注意を払うことを提案します。

3.1 隣接ベクトル

ケース (a1): 重み付けされていないグラフ

重み付けされていないグラフの隣接ベクトルを、偶数の整数 (a[2i]、a[2i+1]、...、i には c 0 の番号が付けられます) の順序付きセットと呼びます。ここで、各数値のペアはは a[2i]、a[2i+1 ] はそれぞれ頂点 a[2i] と a[2i+1] の間のグラフ エッジを指定します。
この記録形式には、グラフが方向付けされているかどうかに関する情報は含まれません (両方のオプションが可能です)。 有向グラフ形式を使用する場合、エッジは a[2i] から a[2i+1] に向かうものとみなされます。 以下: 無向グラフの場合、必要に応じて、頂点を記録する順序の要件を適用できます (たとえば、割り当てられた番号の小さい値を持つ頂点が最初になるなど)。

C++ では、std::vector を使用して隣接ベクトルを指定することをお勧めします。これがこのデータ構造の名前の由来です。

ケース (a2): 重み付けされていないグラフ、エッジの重みは整数です

ケース (a1) と同様に、整数エッジの重みを持つ重み付きグラフの隣接ベクトルを、数値 (a[3i]、a[3i+1]、a[3i+2]、 ...、ここで、i には c 0) の番号が付けられます。ここで、番号 a[3i]、a[3i+1]、a[3i+2] の各「トリプレット」は、a[3i] の番号が付けられた頂点間のグラフのエッジを指定します。と a[3i+1] がそれぞれあり、値 a [3i+2] はこのエッジの重みです。 このようなグラフは、方向を指定することも、方向を指定しないこともできます。

ケース (b): 重み付けされていないグラフ、非整数エッジの重み

異種の要素を一つの配列（ベクトル）に格納することは不可能なので、例えば以下のような実装が可能です。 グラフはベクトルのペアに格納されます。最初のベクトルは重みを指定しないグラフの隣接ベクトルで、2 番目のベクトルには対応する重みが含まれます (C++ の可能な実装: std::pair) ）。 したがって、最初のベクトルのインデックス 2i、1i+XNUMX の下の頂点のペアによって定義されるエッジの場合、重みは XNUMX 番目のベクトルのインデックス i の下の要素と等しくなります。

さて、なぜこれが必要なのでしょうか？

これらの行の作成者は、これが多くの問題を解決するのに非常に役立つことに気づきました。 形式的な観点から見ると、次のような利点があります。

• 隣接ベクトルは、他の「列挙型」構造と同様、非常にコンパクトで、隣接行列 (スパース グラフの場合) よりもメモリの使用量が少なく、実装が比較的簡単です。
• 原則として、グラフの頂点には負の数値をマークすることもできます。 そのような「倒錯」が必要な場合はどうなるでしょうか？
• グラフには、異なる重み (正、負、さらにはゼロ) を持つ複数のエッジと複数のループを含めることができます。 ここには制限はありません。
• エッジにさまざまなプロパティを割り当てることもできますが、詳細についてはセクション 4 を参照してください。

ただし、この「リスト」はエッジへの迅速なアクセスを意味するものではないことを認めなければなりません。 ここで、以下で説明する連想隣接配列が役に立ちます。

3.2 連想隣接配列

したがって、特定のエッジ、その重み、その他のプロパティへのアクセスが重要であり、メモリ要件により隣接行列を使用できない場合は、この問題を解決するために隣接ベクトルを変更する方法を考えてみましょう。 したがって、キーはグラフのエッジであり、整数の順序付きペアとして指定できます。 これはどのように見えますか? 連想配列のキーではないでしょうか？ もしそうなら、それを実装してみませんか? 各キー (順序付けられた整数のペア) が値 (エッジの重みを指定する整数または実数) に関連付けられる連想配列を考えてみましょう。 C++ では、std::map コンテナー (std::map) に基づいてこの構造を実装することをお勧めします。 、int> または std::map 、double>)、または複数のエッジが予期される場合は std::multimap。 そうですね、グラフを保存するための構造は、「行列」構造よりもメモリの使用量が少なく、複数のループとエッジを含むグラフを定義でき、頂点番号の非負性に関する厳密な要件さえありません (わかりません)これを必要とする人はいないでしょうが、それでも）。

4. データ構造はいっぱいですが、何かが不足しています

そしてそれは真実です。多くの問題を解決するとき、グラフの端にいくつかの特性を割り当て、それに応じてそれらを保存する必要があるかもしれません。 これらの特徴を明確に整数に減らすことができれば、隣接ベクトルと連想隣接配列の拡張バージョンを使用して、そのような「追加の特徴を含むグラフ」を保存することができます。

そこで、重み付けされていないグラフを作成します。グラフの各エッジには、たとえば、整数で指定された 2 つの追加の特徴を保存する必要があります。 この場合、隣接ベクトルを「ペア」ではなく、整数 (a[2i]、a[2i+1]、a[2i+2]、a) の「カルテット」の順序付きセットとして定義することができます。 [2i+3]…) 、ここで、 a[2i+2] と a[2i+3] は、対応するエッジの特性を決定します。 エッジの重みが整数であるグラフの場合、順序は通常同様です (唯一の違いは、属性がエッジの重みに従い、要素 a[2i+3] および a[2i+4] によって指定されることです) 、エッジ自体は 4 ではなく 5 つの順序番号で指定されます)。 また、非整数​​のエッジ重みを持つグラフの場合、特徴は重み付けされていないコンポーネントに書き込むことができます。

整数のエッジの重みを持つグラフに連想配列を使用する場合、値として単一の数値ではなく、エッジの重みに加えてその他の必要なすべてを指定する数値の配列 (ベクトル) を指定することができます。特徴。 同時に、非整数の重みの場合の不便な点は、浮動小数点数で符号を指定する必要があることです (はい、これは不便ですが、そのような符号がそれほど多くなく、指定しない場合)あまりにも「トリッキーな」二重に設定しないでください。そうすれば、何も起こらないかもしれません）。 これは、C++ では拡張連想隣接配列を次のように定義できることを意味します。 std::map 、std::vector> または std::map 、std::vector。「キー値ベクトル」の最初の値がエッジの重みになり、その後、その特性の数値指定が配置されます。

文学：

グラフとアルゴリズム全般について:

1. コーメン、トーマス H.、ライザーソン、チャールズ I.、リベスト、ロナルド L.、スタイン、クリフォード。 アルゴリズム: 構築と分析、第 2 版: Trans. 英語から– M.: ウィリアムズ出版社、2011 年。
2. ハラリ・フランク。 グラフ理論。 マ：ミール、1973年。
これらの同じベクトルと隣接関係の連想配列に関する著者のレポートは次のとおりです。
3.チェルヌーホフS.A. グラフを表現および保存する方法としての隣接ベクトルと連想隣接配列 / SA Chernouhov。 グラフを表すデータ構造としての隣接ベクトルと隣接マップ // 国際科学実践会議の論文集「革新的な開発の結果を実装する際の問題とその解決方法」（サラトフ、14.09.2019 年 2019 月 65 日）。 – ステルリタマク: AMI、69、p. XNUMX-XNUMX
このトピックに関する役立つオンライン ソース:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

出所： habr.com