Каков наиболее эффективный способ хранения неориентированного графа?

Question

Как гласит заголовок .. Каков наиболее эффективный способ хранения связанного графа в Java?

Например, допустим, у меня есть несколько мест, соединенных друг с другом различными способами, и мне нужно пройти черезграфик, чтобы увидеть, если он подключен ... любая помощь / комментарий будет полезен, спасибо!

Answer 1

Одним из часто используемых представлений является матрица (двумерный массив), индексируемая всеми узлами графа, где M[i,j] == true, если имеется направленное ребро от узла i до j. Разновидностью темы является сохранение длины / веса края между двумя узлами (где отсутствующий край может быть представлен значением -1).

Answer 2

Использование матрицы инцидент или смежность поможет.

Если вы используете матрицу смежности, разреженная матрица может быть полезна, если у вас много узлов. Кольт обеспечивает реализацию разреженной матрицы. Информация взята из этого ТАК сообщения .

Кроме того, раньше я уже успешно использовал JUNG , так что вы можете заглянуть под капот, чтобы увидеть, как они реализовали ориентированные графы.

Answer 3

использовать матрицу смежности без симметрии, тем самым представляя направление вместо простой смежности.

Answer 4

Я что-то упустил?Данные уже являются графиком, просто сериализуйте его. Для вопроса, как письменные разговоры о матрицах совершенно преждевременно.

Answer 5

Для эффективности поиска - используйте логическую матрицу (true, если есть дуга, соединяющая узлы, false, если ее нет).Для эффективности памяти определите одно из свойств вашего объекта как (динамический) список объектов, на которые он указывает.Обратите внимание, что последнее поможет только в том случае, если на вашем графике много узлов.