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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

Посмотрите на wikipedia. У вас есть различные структуры данных, доступные, а также наследственные сложности

Answer 3

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