ArrayList의 링크에 값을 갖도록 데이터 구조 유지

Question

이것이 내 문제입니다. 나는 그들의 해당 개체에 도시의 이름을 매핑 HashMapVertex의 객체 (이.

나는이 도시 사이의 경로를 모델링 그래프를 확인해야합니다.

나의 현재 구현이 ArrayListEdge의 개체가 이 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 목록을 탐색하고 두 개의 꼭지점이있는 개체를 찾아야합니다.

이 인접 목록 자체에 가장자리 길이를 포함하는 명확한 방법이 있는지 알아보기를 원합니다.

내 Vertex 개체는 정점 당 한 번만 만들어지기 때문에 그 안에 1 개의 가장자리 길이를 저장하면 그 안에 들어있는 다른 모든 가장자리를 덮어 쓸 수 있기 때문에 저장할 수 없습니다. Edge 객체 v1 및 v2 표지 두 정점을 갖기 때문에

Answer 1

: 당신은 항상 대상 정점 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

는, I는 그래프 (에지 v2 버텍스 정점에서 v1 관한) 지시되는 것으로 가정한다.

이렇게 말하면 Edge 자체를 인접 목록에 저장할 수 있습니다. 당신이 어떤 정점을 매핑하는 HashMap<Pair<Vertex, Vertex>, Edge>을 만들 수는 정점 v1와 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을 HashMap s로 사용하고 다른 꼭지점에 값으로 저장된 가장자리 정점을 키로하여 거리를 저장합니다. 접근 방법은 간단하지만 원하는 경우 알고리즘을 게시 할 수 있습니다.