java - 在 Java 中实现边加权图的最佳方式

Question

首先，我正在处理超过 1000 条边的图，我正在遍历邻接列表，以及每秒超过 100 次的顶点。因此，我真的需要一个符合我目标的高效实现。

我的顶点是整数，我的边是无向的、加权的。

我看过 this代码。
但是，它使用边缘对象对邻接列表进行建模。这意味着我必须花费 O(|adj|)当我想获得顶点的邻接点时，|adj|是其相邻元素的基数。

另一方面，我正在考虑使用 Map<Integer, Double>[] adj 为我的邻接列表建模.
通过使用这种方法，我将只使用 adj[v] , v作为顶点，并获取要迭代的顶点的相邻元素。

另一种方法需要这样的东西:

public Set<Integer> adj(int v) 
{
    Set<Integer> adjacents = new HashSet<>();
    for(Edge e: adj[v])
        adjacents.add(e.other(v));
    return adjacents;
}

我的目标是:

• 我想随时根据连通性(相邻节点的数量)对顶点子集进行排序。
• 此外，我需要根据连接自身及其邻居的边的权重对顶点的相邻项进行排序。
• 我想在不使用太多会减慢操作速度的空间的情况下完成这些操作。我应该考虑使用邻接矩阵吗？

Answer 1

我已经将 JGrapht 用作我自己的各种图形表示的库。他们在这里有一个加权图实现:http://jgrapht.org/javadoc/org/jgrapht/graph/SimpleWeightedGraph.html

这似乎可以处理很多您正在寻找的东西，我已经用它来表示最多约 2000 个顶点的图形，它可以很好地满足我的需求，尽管我不记得我的访问率.