2

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

事はです。これが良い方法ではないと誰も考えたことがありませんか？最も推奨される方法は、リストを使用することです。しかし、頂点の間にエッジが1つしかないことを考えると、リストがこれを行うための優れたインターフェイスであるとは思いません。つまり、VertexV1がVertexV2に接続されている場合、エッジは1つだけです。

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

Class Vertex{
    private Set edges;
    private Object data;

    /** Methods**/
}

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

ありがとう！！

編集： また、グラフに繰り返し要素を含めることができないと思われる場合は、挿入時の頂点のルックアップを最小限に抑えるためにHashSetが適しています。

4

3 に答える 3

5

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

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

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

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

于 2010-12-22T13:25:12.920 に答える
2

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

network-simplex-algorithm では、(一連のノードに対する) スパニング ツリーを効率的に表現する必要があります。スパニング ツリーをグラフで表すために、さまざまなデータ構造を使用できます。これらには、次のノード長が含まれます

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

私が遭遇したネットワークシンプレックスアルゴリズムの最も効率的な実装では、これらは配列として表されるのではなく、動的に作成されたメモリブロックのようなものです。

calloc(number_of_nodes, sizeof(struct vertex));

このメモリ割り当てがどのように/どのように実装されているか、つまりリスト/セット/マップであるかどうか、コンパイラの内部で(比較的低いレベルで)わかりません。

つまり、要約すると、グラフを実装する最良の方法は、実行する操作に大きく依存します。

ネットワーク シンプレックス アルゴリズムと、それを効率的に実装するために必要なデータ構造については、この本で説明しています。

于 2010-12-22T13:37:00.440 に答える
1

最も抽象的に言えば、セットには要素がセット内にあるかどうかをテストする述語があります。ユニオンとインターセクションを提供する演算子もサポートする場合があります。差は計算可能である必要はありません。

最も抽象的には、List は反復、サブリスト、および追加をサポートします。

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

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

一部のグラフベースのシステムは、基本的なメカニズムとしてセットを使用しますが、有限グラフではなく無限グラフを扱っており、内包セットが有用になります。

于 2010-12-22T13:25:39.380 に答える