维护数据结构以在 ArrayList 的链接上具有值

Question

这是我的问题。我有 HashMap 个 Vertex 个对象（将城市名称映射到相应的对象。

我需要制作一个图表来模拟这些城市之间的路线。

我当前的实现有一个 ArrayList 个 Edge 个对象，每个对象有两个 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 个边长会覆盖进入其中的所有其他边。

Answer 1

由于 Edge 对象有两个标记为 v1 和 v2 的顶点，我假设该图是有向的（边从顶点 v1 指向顶点 v2).

也就是说，您可以将 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 2

假设顶点 v1 和 v2 之间只有一条边，您可以创建一个 HashMap<Pair<Vertex, Vertex>, 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<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 3

您也可以使用 HashMap 的 HashMap 并将边顶点作为值存储到另一个顶点的距离作为键保存。该方法很简单，但如果您愿意，我可以 post 算法。

维护数据结构以在 ArrayList 的链接上具有值

Maintaining a data structure to have the values on links of ArrayList

java

graph

adjacency-list