3

こんにちは私はコースのグラフデータ構造を実装しようとしています（グラフは要件の一部ではありません。問題に取り組むためにグラフを使用することを選択しました）。最初に考えたのは、隣接リストを使用して実装することでした。必要なメモリが少なくて済み、グラフにそれほど多くのエッジがあるとは思わないからです。

しかし、それは私に起こりました。マップを使用して隣接リストグラフのデータ構造を実装できます（HashMap具体的には）。頂点のリストの代わりに、頂点のマップがあります。これは、頂点へのエッジの短いリストを保持します。

これが私にとっての道のようです。しかし、私などの学生がこれに使用する際に見逃したかもしれない欠点を誰かが見ることができるかどうか疑問に思いましたHashMapか？（残念ながら、私たちが調査している間、非常に疲れていたことを思い出しHashMapます...したがって、それらについての私の知識は、私が知っている他のすべてのデータ構造よりも少ないです。）だから私は確信したい。

ちなみに私はJavaを使っています。

4

2 に答える 2

9

グラフを表す2つの主な方法は次のとおりです。

  • 隣接リスト付き（あなたが言ったように）
  • 隣接行列を使って

エッジが多すぎない（つまり、グラフを表す隣接行列がまばらになる）ので、行列の代わりにリストを使用するという決定は、あなたが言ったように、実際に占めるスペースが少なくなるので、良いものだと思います。存在しないエッジを表すためにスペースが無駄になることはありません。さらに、各グラフを接続先のリストにMapマップできるため、このアプローチは論理的であるように思われます。もう1つの方法は、各オブジェクトに、接続先のノードのリストをデータフィールドとして含めることです。これらのアプローチのどちらでもうまくいくと思います。以下にまとめました。NodeNodeNode

最初のアプローチ（マップを維持する）：

Map<Node, Node[]> graph = new HashMap<Node, Node[]>();

2番目のアプローチNode（クラスに組み込まれたデータ）：

public class Node {
    private Node[] adjacentNodes;
    public Node(Node[] nodes) { adjacentNodes = nodes; }
    public Node[] adjacentNodes() { return adjacentNodes; }
}
于 2012-08-30T02:16:27.697 に答える
7

グラフは従来、隣接リストまたは隣接行列のいずれかを介して表されます（ノードIDに順番にラベルが付けられている場合や、ノード/エッジの数が事前にわかっている場合など、特定のグラフ形式に最適化される方法は他にもあります。しかし、私はそれには入りません）。

隣接リストと隣接行列のどちらを選択するかは、ニーズによって異なります。明らかに、隣接行列は隣接リストよりも多くのスペースを占有します（行列は常に（ノードの数）^ 2を取りますが、リストは（ノードの数+エッジの数）を取りますが、グラフが「小さい」場合はそれは実際には違いはありません。

もう1つの懸念は、エッジがいくつあるか（グラフがまばらか密か）です。グラフの密度は、持っているエッジの数を取得し、それを次のように割ることでわかります。

n（n-1）/ 2

ここで、「n」はグラフのノード数です。上記の式は、「n」ノードの無向グラフで可能なエッジの総数を求めます。グラフが指示されている場合は、「/2」を削除します。

他に考えるべきことは、効率的なエッジメンバーシップが重要かどうかです。隣接リストは、単なる配列ルックアップであるため、エッジメンバーシップを簡単に検出できます（O（1））。隣接リストの場合、「リスト」がそれ以外のものとして格納されているHashSetと、エッジリスト全体。または、エッジリストを並べ替えたままにして、バイナリ検索を実行することもできますが、エッジの挿入に時間がかかります。グラフが非常にまばらで、隣接行列が大量のメモリを使用している可能性があるため、隣接リストを使用する必要があります。考えるべきことがたくさんあります。

あなたのプロジェクトに関連するかもしれないもっと多くの懸念があります、私はほんのいくつかをリストします。

一般に、グラフがそれほど複雑または「大きく」ない（数百万のノードの意味で）と仮定するとHashMap、キーはノードIDであり、値はSetキーの隣接ノードを示すノードIDのその他のコレクションです。ノードは問題ありません。8GBのマシンで400,000以上のノードグラフに対してこれを実行しました。ベースのHashMap実装は、おそらく実装が最も簡単です。

于 2012-08-30T03:14:04.837 に答える