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

Question

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

• таблица с именем Q поместить туда все узлы в самом начале. В каждом цикле узел посещается и в конце цикла он удаляется из Q.

• Таблица с именем Key, по одному для каждого узла. При необходимости ключ изменяется (по крайней мере, один раз за цикл).

• Таблица с именем Parent, по одному для каждого узла. В каждом цикле в эту таблицу вставляется новый элемент.

• Таблица с именем A. Программа хранит здесь конечные края минимального остовного дерева. Это таблица, которая возвращается.

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

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

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

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

Answer 1

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

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

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

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

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