85

私は現在、技術的なプログラミング面接の準備に関するSteve Yeggeのアドバイスに従っています：http ：//steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

グラフに関する彼のセクションで、彼は次のように述べています。

メモリ内のグラフを表現するための3つの基本的な方法（オブジェクトとポインタ、マトリックス、および隣接リスト）があり、各表現とその長所と短所をよく理解する必要があります。

行列と隣接リストの表現の長所と短所はCLRSで説明されていますが、これらをオブジェクトの表現と比較するリソースを見つけることができませんでした。

考えてみるだけで、自分で推測することもできますが、大切なことを見逃していないことを確認したいと思います。誰かがこれを包括的に説明するか、そうするリソースを私に指摘することができれば、私はそれを大いに感謝します。

4

4 に答える 4

98

オブジェクトとポインター

これらは、他の回答で hammar が述べたような基本的なデータ構造にすぎJavaません。これは、エッジや頂点などのクラスで表現します。たとえば、エッジは 2 つの頂点を接続し、有向または無向のいずれかであり、重みを含むことができます。頂点には ID や名前などを付けることができます。ほとんどの場合、両方に追加のプロパティがあります。したがって、次のようにグラフを作成できます

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30

このアプローチは、オブジェクト指向のユーザーにとってより読みやすく便利であるため、オブジェクト指向の実装に一般的に使用されます;)。

マトリックス

行列は単純な 2 次元配列です。次のような int 配列として表すことができる頂点 ID があると仮定します。

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

これは一般に、インデックス アクセスが必要な高密度グラフに使用されます。これで無向・無向・加重構造を表現できます。

隣接リスト

これは単純なデータ構造の組み合わせにすぎません。通常、HashMap<Vertex, List<Vertex>>. HashMultimap同様に、グアバでも使用できます。

O(1) (償却された) 頂点ルックアップがあり、要求したこの特定の頂点に隣接するすべての頂点のリストが返されるため、このアプローチはクールです。

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

これはスパース グラフを表すために使用されます。Google で申請する場合は、Web グラフがスパースであることを知っておく必要があります。BigTableを使用すると、よりスケーラブルな方法でそれらを処理できます。

ああ、ところで、これはこの投稿の非常に良い要約です ;)

于 2011-05-04T17:23:39.310 に答える
7

オブジェクトとポインターは、少なくともこれらの表現を使用するアルゴリズムを比較する目的では、隣接リストとほとんど同じです。

比較

struct Node {
    Node *neighbours[];
};

と

struct Node {
    Node *left;
    Node *right;
};

後者の場合、名前付きポインターよりも操作が簡単な場合は、オンザフライでネイバーのリストを簡単に作成できます。

于 2011-05-04T15:57:23.490 に答える
4

オブジェクト表現 (インシデンス リスト) の利点は、隣接する 2 つの頂点がエッジの同じインスタンスを共有することです。これにより、無向エッジ データ (長さ、コスト、フロー、さらには方向) を簡単に操作できます。ただし、ポインタ用に余分なメモリを使用します。

于 2011-06-18T13:44:38.687 に答える