Списки смежности в джава
При решении задач на графы используются списки смежности.
В C++ список смежности находится в массиве векторов:
vector<int> adj[n];
и заполняется этот массив векторов так:
adj[1].push_back(2);
Как это реализовать на java?
Ответы (1 шт):
Основным различием между 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);