Java-реализация списка смежности

Вот простая реализация для создания списка смежности. Согласно проблеме:

Будет n связанных списков, каждый из которых имеет переменный размер.

Сначала инициализируйте ArrayList связанных списков целых чисел:

ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

Затем просто добавьте связанные списки, повторив следующий код:

adj_list.add(new LinkedList<Integer>());

Если вы используете его для представления графа, то количество связанных списков = количество вершин. Таким образом, вы должны повторить приведенную выше строку n (количество вершин) раз.

Скажем, теперь вы хотите добавить числа 3,4,5 в свои первые связанные списки. Сделайте следующее:

adj_list.get(0).add(3);
adj_list.get(0).add(4);
adj_list.get(0).add(5);

Это просто означает, что в вашем графе есть ребро от вершины 0 до 3,4,5.

Во-первых, ваше описание похоже на матрицу смежности, за исключением того, что вы говорите m на n. Матрицы смежности всегда квадратные, поэтому мы должны принять m==n. Элементы матрицы являются весами ребер.

Представление графа списком смежности (обычно) представляет собой массив adj наборов пар. Множество adj[i] содержит пару <j, w> тогда и только тогда, когда существует направленное ребро i--w-->j, т.е. из вершины i в j с весом w в представленном графе.

С этим определением становится ясно, что вы должны начать с n пустых наборов смежности adj[i], а затем пройтись по матричным элементам m[i][j] = w. Для каждого из них добавьте <j, w> к adj[i].

Java-код для этого довольно тривиален, поэтому я не буду его писать. Тип графа, представленного списками смежности, что-то вроде ArrayList<HashMap<Integer, Integer>> adjacencies. Пары <j,w> in adj[i] представляют собой сопоставления j -> w, хранящиеся в хэш-таблице adjacencies.get(i). Код для создания такой смежности будет adjacencies.get(i).put(j, w).

Этот метод позволяет перебирать вершины, соседние с i, перебирая ключи в хеш-таблице adjacencies.get(i), искать вес данного ребра i--w-->j с w = adjacencies.get(i).get(j) и т. д. для всех обычных операций с графом.