Javaのグラフ表現

グラフ（データ構造）を使用するアプリケーションを作成する必要がありますが、その表現方法はわかりませんし、ヒントをいくつか教えてください。Javaのグラフ表現

クラスVertexとEdgeを作成する必要がありますか？はいの場合は、その属性は何ですか？

出典

2012-03-03 Andre Roque

Iはグラフの隣接リストを使用して示唆しています。

最も簡単な方法は、隣接する頂点へのリンクリストArrayList<Vertex>を含むVertexクラスを作成することです。これはグラフを表現するのに十分ですが、別のEdgeクラスは必要ありません。

頂点クラスに他のデータ属性を追加できますが、リンクのリストは厳密に必要なものです。

有向枝（一方向リンク）または無向枝（隣接する頂点が互いに向かい合っている）を持つことができます。私の疑問は、私のようなコードを、作る方法です

出典

2012-03-03 09:50:59 mikera

私は上記のグラフの実装に疑問がありました。無向グラフの場合、addEdge関数を実装すると、同じ関数の両方向にエッジを追加する必要がありますか？ – ueg1990

@ ueg1990 - あなたはそうすることができます。それはあなたのデータ構造に依存しますが、確かに双方向ポインタを持つためにいくつかのグラフ検索をスピードアップすることができます。これを行うもう1つの方法は、各無向エッジが、頂点aおよびbがソートされた順番（例えば、頂点IDによってソートされている）である（a、b）として一度格納されるリストである。 – mikera

しかし、無向グラフの場合、aからbへの辺がある場合、定義上、bからaへの辺を追加する必要があります。 – ueg1990

これはJavaに固有のものではありません。 2つの最も一般的な表現は、隣接行列とリストです。詳細here

ライブラリをしたい場合は、JGraphTあなたはそれを一般的な方法を表すことができ、素敵な

出典

2012-03-03 09:33:10

LIKE「グラフデータベース」を試してみて、活用することがあります：パブリッククラス頂点{ を.. 。 } パブリッククラスエッジ{ ... } もしそうなら、私は属性として何を入れますか。ちなみに、目的はPrimのアルゴリズムで最小スパニングツリーを作ることです。どのような表現が良いですか？ –

私はライブラリや何かを使わないように、自分自身で構造を作っているはずです –

です。 See here。例えば：

adjacency matrixは（Javaで2次元配列を使用：[][]）を（Javaで：Listを使用）
adjacency list

出典

2012-03-03 09:33:59 Bozho

これはかなりあなたのユースケースに依存しますが、neo4j

出典

2012-03-03 10:03:34

（自分で構造を作らなければならないことは分かっていますが、同じ質問のある人はそうでないかもしれません:)） –

Javaのグラフ表現

答えて

関連する問題