Java: структура данных для минимального связующего дерева

Question

Мой проект - реализовать минимальное связующее дерево с использованием Java. Я стремлюсь использовать алгоритм Прима для выполнения задачи.

Определение графа G = (V, E), где V - набор контактов, E - набор возможных взаимосвязей между парами контактов, и для каждого ребра (u, v) в E мы имеем взвешивать w (u, v) с указанием стоимости подключения u и v.

Моя идея - использовать два хэш-карты. Сначала в качестве ключа будет указан pin, а в качестве значения указан список соседей. Второе хеш-изображение будет принимать список ребер (u, v) в качестве ключа, а значением будет его вес.

Как вы думаете, как лучше хранить график?

Answer 1

Графики обычно (без учета алгоритма, используемого с этими графами) хранятся в виде:

• списков смежности,
• матриц смежности,
• списков заболеваемости,
• матрицы инцидентности.

Все они имеют свои преимущества и недостатки, касающиеся использования памяти и времени, необходимого для их обхода. Википедия отлично написана на графических представлениях в компьютерах.

Answer 2

Для алгоритмов минимального связующего дерева Крускала и Прима достаточно представления графа в виде списка смежности. Это более эффективно в использовании памяти, чем подход Матриса. Так что это хороший выбор в вашем случае.

Answer 3

Посмотрите на Википедию .Вам доступны разные структуры данных, а также унаследованные сложности