java 中的哪个标准库数据结构为实现邻接表提供了最小的时间复杂度？

Which standard library data structure in java provides minimum time complextiy for implementing adjacency list?

我是图论新手。我遇到过很多方法来说明 java 中图的邻接表表示的实现，其中包括：

ArrayList<T>[]
LinkedList<T>[]
ArrayList<ArrayList<T>>
ArrayList<HashSet<T>>
HashMap<Integer, List<T>>
etc.

如果我需要在图形上最少执行这些操作，我想知道哪种数据结构是获得最佳时间复杂度的最佳数据结构：

  1. 判断两个节点是否由边连接。
  2. 迭代特定顶点的所有邻居。
  3. （可选）按权重对顶点的所有邻居进行排序，或者像优先队列一样。

您能否指导哪种标准库数据结构最适合 java 中图的邻接表实现以获得最佳 space 和时间复杂度？ （时间复杂度优先于space复杂度）

为简单起见，创建一个包含 TreeMap 的节点 class，该 TreeMap 保存对其连接的节点的引用。

  1. 找出两个节点是否连接只需选择一个节点并查询映射 O(log(n))。
  2. 遍历所有邻居是在地图上行走 O(n)。
  3. TreeMap 进行自然排序，因此选择您的值并让比较器使用该值进行排序。

无论如何，根据您提供的信息。

我会说 LinkedHashSet<LinkedHashSet<T>>。这是因为：

  1. 判断两个节点是否由一条边连接：调用内部集合的contains()方法解决这个问题，所需时间O(1)
  2. 迭代特定顶点的所有邻居：后续调用 iterator.next()，每个调用花费 O(1)
  3. 按权重排序顶点的所有邻居，或者像优先队列一样：如果你需要这个，将你的内部实现更改为 TreeSet<T> 并在你的节点上实现 Comparable 接口 class。 TreeSet 允许您在 O(log n) 中执行所有操作，但您的所有项目都将被排序。

来源：Java Generics and Collections