1

私は最近、大学院の隣でソフトウェア開発の練習をするために、グラフ（隣接行列や単なる数値ではなく、両方ともオブジェクトで表されるノードとエッジ）をモデル化するためのツールを書き始めました。ノードにその隣接ノードとそれが付随するエッジを知ってもらいたいのですが。これを行うための明白な方法は、HashSetとHashSetを使用することです。しかし、私がやりたいのは方法を持っていることです

Node_A.getEdge(Node B)

これは、O（1）のノードAとBの間のエッジを返します。これを行うには、ノードを隣接ノードに接続するエッジに隣接ノードをマップする1つのHashMapを使用して、上記の2つのHashSetを置き換えることを考えていました。たとえば、

Node_A.hashmap.get(B)

AとBをつなぐエッジを返す必要があります。ここでの私の問題は、

HashMap.keySet().contains(Node A);
HashMap.values().contains(Edge e);

どちらもO（1）で動作しますか？それが標準ライブラリの場合ではない場合、keySet（）とvalues（）の追加、削除、包含、サイズの一定の時間を与える実装はありますか？

4

2 に答える 2

1

これを考えすぎないようにしてください。たとえば、AとBの間のエッジをによって取得すると言っていますNode_A.getEdge(Node B)。しかし、通常、エッジと見なされるのはA- >B情報です。（したがって、取得する必要のある情報が必要です。）

当然のことながら、O（1）が必要だと言いますが、明らかに隣接行列を格納するとO（n）しか得られないため、それを使用することはできません。しかし、各ノードオブジェクト内に隣接ノードのリストを保存することで、すでに2番目に明白な選択肢が、必要なものを提供します。（注：これは、O（n）を提供するグローバル隣接リストを持つこととは異なります）。

于 2012-10-20T18:59:20.073 に答える
1

AmitDが言ったように、HashSetとHashMapは、contains、get、putに対して一定の時間を持っています。たとえば、GoogleGuavaライブラリのHashBiMapHashMap.valueSet().contains(Edge e)を調べてみてください。

于 2012-10-20T19:00:02.370 に答える