主页 / 问题 / 1604156
Accepted
kazosh
Asked:2025-01-06 03:04:44 +0000 UTC2025-01-06 03:04:44 +0000 UTC

Java 中的邻接表

  • 772

解决图问题时，会使用邻接表。
在 C++ 中，邻接表位于向量数组中：

vector<int> adj[n];

这个向量数组的填充如下：

adj[1].push_back(2);

如何在java中实现这个？

java

1 个回答

  1. Best Answer

    在这种情况下，C++ 和 Java 之间的主要区别在于，在 C++ 中，使用创建的数组vector<int> adj[n];已经填充了将调用默认构造函数的对象，而在 Java 中，必须手动填充数组（或集合）。

    另外，在Java中你不能直接创建类型为泛型对象的数组List<Integer>[] adj = new List<Integer>[n]，创建列表的列表（动态数组）并正确初始化它更容易。
    因此，要访问此类列表的元素，您必须使用该方法List::get而不是索引运算符[]

    int n = 10;

List<ListInteger> adj = new ArrayList<>(n); // создаётся пустой список связности с заданной ёмкостью
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

adj.get(1).add(2);

// Stream API
List<ArrayList<Integer>> adj2 = Stream.generate(ArrayList<Integer>::new).limit(n).toList();

adj2.get(0).add(1);

    当然，如果您使用带有整数键的映射，则可以避免不必要的初始化和连接列表元素的构造，正如 Alex Krass 在他的评论中建议的那样。地图有一个方法Map::computeIfAbsent，允许您在必要时创建元素：

    Map<Integer, List<Integer>> adj = new HashMap<>();
// аналог adj[1].push_back(2);
adj.computeIfAbsent(1, k -> new ArrayList<>()).add(2);
    • 0

相关问题