Кодирование связанных узлов в графе

Возможно, дубликат Хорошая библиотека алгоритмов графа Java?. Короткий ответ - посмотреть на JGraphT.

Создайте класс Node и дайте ему переменную экземпляра типа Node. Инициализировать его значением null - если указанный узел подключен к другому узлу, то эта переменная экземпляра будет ссылаться на него; в противном случае он останется нулевым.

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

Два наиболее распространенных способа представления графа - это матрица смежности и списки смежности. Пусть n будет количеством узлов.

Матрица смежности A - это матрица логических значений размера n x n, такая что A (i, j) = 1, если узлы i и j соединены, и 0, если они не соединены.

В представлении списков смежности для каждого узла вы поддерживаете список узлов, с которыми он связан (смежных).

Теперь вопрос в том, что вы хотите делать с графиком. Если это что-то простое, возможно, имеет смысл раскатать собственное. Если нет, вы можете поискать в Интернете библиотеку Java для обработки графиков. Был упомянут JGraphT.

Если вы хотите использовать матрицу смежности, вы можете легко представить ее на Java как двумерный массив значений типа bool или int. Вам нужно будет дать каждому узлу индекс. Самый простой способ для этого нужно хранить объекты Node в массиве всегда в одном и том же порядке. Таким образом, у вас действительно будет две структуры данных: массив узлов, которые представляют собой объекты, представляющие то, чем на самом деле являются ваши узлы, и матрица смежности, которая ссылается на узлы по их индексам.

После заполнения матрицы вы можете легко найти узел, который связан с большинством других узлов, сложив значения (0 и 1) во всех столбцах (или строках) и найдя максимум. Надеюсь это поможет.

Есть две стандартные модели хранения графиков. Том описывает Список смежности. Другой будет автономным Матрица смежности.

Если вы заботитесь об эффективности, изучите разреженность вашей ситуации (чем больше граней, тем более удобна для производительности матричная версия). Если перфоманс не является проблемой, используйте то, что вы предпочитаете программировать ...