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

Question

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

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

我当前的实现有一个 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.

但是在这个模型中，我的邻接表不存储邻接表中的边长，所以每次我想要边长时，我都必须遍历边列出并找到其中包含两个顶点的对象。

我想弄清楚是否有一种干净的方法可以将边长包含在此邻接表本身中。

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

Answer 1

由于 Edge 对象有两个标记为 v1 和 v2 的顶点，我假设该图是有向的(边从顶点 指向code>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);
}