维护数据结构，使其具有ArrayList链接上的值

Question

这是我的问题。我有一个vertex对象的hashmap（将城市名称映射到相应的对象）。

我需要做一个图形来模拟这些城市之间的路线。

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.

因为我的vertex对象每个顶点只创建一次，所以我不能在其中存储，因为在其中存储1个边长度将覆盖进入其中的所有其他边。

Answer 1

假设在顶点v1和v2之间只有一条边，您可以创建一个HashMap ,edge> 来映射通过边连接的顶点。

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 (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);
}