グラフの教え方に疑問を抱く

Question

私はアルゼンチン出身ですが、データ構造のクラスを受講したことのある人は皆、グラフが何であるかを知っていると思います。そうすれば、どのような実装が「一般的」または「標準」であるかがわかるかもしれません。リストまたは配列を通じて実装できます。ウィキペディアにもこう書いてあります。マーク・アレン・ワイス、ブルーノ・プライス、ルイス・ジョヤネス・アギラールも同様だ。

事はそうです。これが良い方法ではないと考えたことのある人はいないでしょうか?最も推奨される方法は、リストを使用することです。しかし、頂点間にエッジを 1 つだけ持つことができることを考慮すると、List がこれを行うための良いインターフェイスであるとは思えません。つまり、頂点 V1 が頂点 V2 に接続されている場合、エッジは 1 つだけ存在します。

リストではなくセットになると思いませんか?

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

いくつか意見を知りたいのですが、どう思いますか？

ありがとう！！

編集： また、グラフに繰り返し要素を含めることはできないと考えられる場合、挿入時の頂点の検索を最小限に抑えるには、HashSet が適切な選択となります。

Answer 1

頂点の隣接関係はセット (マルチグラフの場合はマルチセット) によって最も正確にモデル化されるというご指摘は正しいです。では、なぜデータ構造の本では配列やリンク リストについて書かれているのでしょうか?理由は 3 つ考えられます。

1. プログラミング言語にプリミティブ データ型としてセットを含めるべきだという考えは、か​​なり最近のものです。昔の作家はそれを使用することを考えなかったでしょうし、現代の作家はこの分野の伝統に従う傾向があります。

2. データ構造コースの目的の 1 つは、高い (抽象) レベルだけでなく低い (具体的な) レベルでもデータの表現について考えることができるようにすることです。セットは、(リンクされたリストや配列とは異なり) 明らかな低レベル実装を持たない抽象データ型です。一部のセットはリンク リストとして表現するのが最適であり、一部はハッシュ テーブルとして、一部は配列として表現するなどです。したがって、データ構造のコースでは、セットの高レベルの表現を飛ばして低レベルの実装に移るのは自然なことですが、セットを使用するアルゴリズムの動作を分析するには、とにかくそれについて知っておく必要があります。

3. アルゴリズムは特定の表現を使用することで最も効率的に表現できるため、データ型の表現方法について独断的にならないことが重要です。例1.長さのパスをカウントするには n グラフ内の頂点の各ペアの間で、グラフをその隣接行列で表し、行列をべき乗します n. 。頂点の隣接関係をエッジのセットとして表現することにこだわる場合は、このアルゴリズム (標準的な手法を使用して並列化できます) を見逃すことになります。例2。クヌートさんの「ダンシングリンクス正確なカバー問題のアルゴリズムは、二重リンク リストを使用して列のセットを表すため、削除された項目からのリンクを再利用して効率的にバックトラッキングできます。

Answer 2

比較的 より高い C/C ++プログラマーレベル、グラフ/ネットワークの実装方法は、実行される操作に大きく依存します。自分自身であることで、私はおそらくここで私の回答/例に偏っています。グラフ/ネットワークに実装できる最も効率的なアルゴリズムの一部は、多項式時間アルゴリズムです。すべてではないにしても、ほとんどの場合、私が考えることができる多項式時間アルゴリズム（Dijkstraの最短経路問題、輸送問題、最大流の問題など）は、最小コスト（MCF）問題の特別なケースです。計算上、MCF問題を解決する最も効率的な方法の1つは、ネットワークシンプルなアルゴリズム（それ自体が一般的な線形プログラムを解くためのシンプレックスアルゴリズムの専門化です）を介してです。

Network-Simplex-Algorithmでは、スパニングツリー（ノードのセット上）を効率的に表現する必要があります。グラフ内のスパニングツリーを表すために、さまざまなデータ構造を使用できます。これらには、次のノード長が含まれます

predecessor[], thread[] and depth[] arrays.

私が出会ったネットワークシンプルなアルゴリズムの最も効率的な実装では、これらは配列としてではなく、動的に作成されたメモリのブロックを介して表現されます

calloc(number_of_nodes, sizeof(struct vertex));

私は確信が持てません（比較的 低い レベル）コンパイラの内部何/このメモリ割り当ての実装 - リスト/セット/マップであるかどうか。

したがって、要約すると、 一番 グラフを実装する方法は、実行する操作に大きく依存しています。

ネットワークシンプレックスアルゴリズムと同じものを効率的に実装するために必要なデータ構造は、 この本.

Answer 3

最も抽象的に、セットには、要素がセット内にあるかどうかをテストする述語があります。また、組合と交差点を提供するオペレーターをサポートする場合があります。違いは計算可能ではありません。

最も要約では、リストは反復、サブリスト、および付録をサポートしています。

グラフ上のほとんどのアルゴリズムでは、エッジを反復する必要があるため、反復をサポートする構造が推奨されます。ほとんどのアルゴリズムは同じエッジを2回追加しようとしないため、複製の除去は必要ありません。

もちろん、ライブラリのほとんどのセットは有限の拡張セットであり、反復もサポートするため、それらを使用できますが、重複をチェックするコストがかかります。

一部のグラフベースのシステムは、根本的なメカニズムとしてセットを使用しますが、インターションセットが有用になる有限のグラフではなく、無限のグラフを扱っています。