Какова наиболее эффективная структура данных для разработки алгоритма PRIM?

Question

Какова наиболее эффективная структура данных для разработки алгоритма PRIM?

Я проектирую Graph в c ++, используя хеш-таблицу для его элементов. В хеш-таблице используется открытая адресация, а граф имеет не более 50 000 ребер. Я также разработал алгоритм PRIM, чтобы найти минимальное остовное дерево графа. Мой алгоритм PRIM создает хранилище для следующих данных:

Стол с именем Q положить туда все узлы в начале. В каждом цикле посещается узел, и в конце цикла он удаляется из Q.
Стол с именем Keyпо одному на каждый узел. Ключ изменяется при необходимости (по крайней мере, один раз за цикл).
Стол с именем Parentпо одному на каждый узел. В каждом цикле новый элемент вставляется в эту таблицу.
Стол с именем A, Программа хранит здесь конечные ребра минимального остовного дерева. Это таблица, которая возвращается.

Какую структуру данных наиболее эффективно использовать для создания этих таблиц, если предположить, что граф имеет 50 000 ребер?

Могу ли я использовать массивы?

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

Но опять же, элементы являются способом для многих. Мой алгоритм хорошо работает для графов, состоящих из нескольких узлов (10 или 20), но я скептически отношусь к ситуации, когда графы состоят из 40 000 узлов. Любое предложение высоко ценится.

0

c++data-structures graph hashtable minimum-spanning-tree

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

Я только что просмотрел документацию для STD
http://en.cppreference.com/w/cpp/container/priority_queue
чтобы увидеть, были ли функции, которые я всегда хочу добавить, в какой-то форме, которую я раньше не замечал (или был добавлен в какой-то недавней версии C ++). Насколько я могу сказать, НЕТ. В большинстве случаев использования приоритетной очереди в реальном мире (конечно, моей) требуются незначительные дополнительные функции, которые я понятия не имею, как использовать стандартную версию. Поэтому мне нужно было переписать его с нуля, включая дополнительные функции. Но это на самом деле не сложно.

Метод, который я использую, был заново изобретен многими людьми (я делал это в Си в 70-х, и не был первым). Быстрый поиск в Google нашел одно из многих мест, где мой подход описан более подробно, чем я описал его.
http://users.encs.concordia.ca/~chvatal/notes/pq.html#heap

0