ArrayListのリンク上の値を持つデータ構造を維持する

Question

これは私の問題です。私はそれに対応するオブジェクトへの都市の名前をマッピングする（HashMapVertexのオブジェクトを持っている。

私はこれらの都市間のルートをモデル化し、グラフを作成する必要があります。

私の現在の実装では、持っているArrayListEdgeのオブジェクトを持っています2 Vertexと、各オブジェクトのパスコスト。私はその後、VertexとEdgeオブジェクトのこれらのセットを使用して隣接リストを作る、すなわち

for (Edge e : edges) { 
    ArrayList<Vertex> list = adjList.get(e.v1); 
    if (list == null) 
     list = new ArrayList<>(); 
    list.add(e.v2); 
    adjList.put(e.v1, list); 
} 

edges: ArrayList of edges having (v1,v2,weight) in each object 
list : The adjacency list for the vertex v1. 
adjList: HashMap which has all the lists index by the vertex. 

しかし、このモデルでは、私の隣接リスト隣接長リストに辺の長さを格納しないので、辺の長さを求めるたびに、edgesリストを走査し、2つの頂点を持つオブジェクトを見つけなければなりません。

この隣接リスト自体にエッジの長さを含めるきれいな方法があるかどうかを知りたいと思います。

私のVertexオブジェクトは1頂点につき1回しか作成されないので、その中に1辺の長さを格納すると、その中に入る他のすべての辺を上書きするため格納できません。

Answer 1

あなたが頂点をマップHashMap<Pair<Vertex, Vertex>, Edge>を作成することができ頂点v1とv2の間に一つだけのエッジを持っていると仮定すると、エッジを介して接続される。あなたはまたに関係の逆を追加することができ無向グラフならば

HashMap<Pair<Vertex, Vertex>, Edge> vertexMap = new HashMap<>(); 

for (Edge e : edges) { 
    Pair<Vertex, Vertex> key = new Pair<>(e.v1, e.v2); 
    vertexMap.put(key, e); 
} 

あなたはvertexMap.get(new Pair<Vertex, Vertex>(v1, v2))

Pairを経由して頂点に与えられたエッジを検索することができますこの方法は、

class Pair<K, V> { 
    private final K first; 
    private final V second; 

    public Pair(K first, V second) { 
     this.first = first; 
     this.second = second; 
    } 

    public K getFirst() { 
     return first; 
    } 

    public V getSecond() { 
     return second; 
    } 

    @Override 
    public int hashCode() { 
     int hash = 7; 
     hash = 89 * hash + Objects.hashCode(this.first); 
     hash = 89 * hash + Objects.hashCode(this.second); 
     return hash; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (obj == null) { 
      return false; 
     } 
     if (getClass() != obj.getClass()) { 
      return false; 
     } 
     final Pair<?, ?> other = (Pair<?, ?>) obj; 
     if (!Objects.equals(this.first, other.first)) { 
      return false; 
     } 
     if (!Objects.equals(this.second, other.second)) { 
      return false; 
     } 
     return true; 
    } 
} 

ように実装することができループ：

for (Edge e : edges) { 
    Pair<Vertex, Vertex> keyInverted = new Pair<>(e.v2, e.v1); 
    vertexMap.put(keyInverted, e); 
} 

Answer 2

Edgeオブジェクトがv1とv2を標識した2つの頂点を有しているので、私は（エッジがv2を頂点に頂点v1から導かれる）グラフが向けられていると仮定する。

これは、Edge自体を隣接リストに保存することができると言われています。あなたはいつも何の問題以降のコードでリストの処理が存在しない先の頂点がv2であることを知っている：

for (Edge e : edges) { 
    ArrayList<Edge> list = adjList.get(e.v1); 
    if (list == null) 
     list = new ArrayList<>(); 
    list.add(e); // add the edge which contains the adjacent vertex and the weight 
    adjList.put(e.v1, list); 
} 

Answer 3

代わりにHashMapをHashMapsと使用し、他の頂点の値として格納されたエッジ頂点をキーとして距離を保存することもできます。このアプローチは簡単ですが、必要に応じてアルゴリズムを投稿できます。