алгоритм — Проектирование структур данных для реализации Prim в Stack Overflow
Я пытаюсь реализовать алгоритм Прима для MST в C ++. У меня вопрос по дизайну
Я реализовал min-heap, которая принимает целое число, и мы можем извлечь min, уменьшить ключ и вставить ключ.
Теперь, как я понимаю в Приме, мне нужно поддерживать вес, информацию о соседях для каждой вершины. У меня есть несколько идей:
1] Определить структуру
struct node {
int vertex;
int weight;
int neighbor;
};
Используйте минимальную кучу, чтобы вернуть узел с минимальным весом. Но проблема заключается в уменьшении ключа, так как для уменьшения ключа вызывающему абоненту необходимо передать вершину, для которой он хочет уменьшить ключ. Поскольку куча слишком часто меняет элементы, мне нужно просмотреть весь список, чтобы найти вершину, а затем уменьшить ее ключ. Это O (N), я думаю, что Прим будет хуже, если я сделаю это.
2] Другой способ — сохранить другой массив, который отслеживает положение вершины в очереди с минимальной кучей. Но было бы неудобно отслеживать позиции во время операций с минимальной кучей.
В основном, если мне нужно сделать ключ уменьшения (v), как найти v в очереди минимальной кучи, которая основана на весе. Так есть ли какой-нибудь элегантный способ сделать это? который еще может сохранить сложность?
Решение
По сути, вам действительно нужно сделать несколько перекрестных ссылок между структурами данных. Тем не менее, вы пишете
Но было бы громоздко отслеживать позиции во время операций с минимальной кучей
что не совсем правильно. Используя следующее, вы можете повторно использовать или записывать повторно используемые структуры данных, которые не требуют этого.
-
Начнем с того, что ваша приоритетная очередь должна быть итератор, который позволяет O (1) доступ. Для этого вы можете использовать
boost.Heapнапрямую (см. примечание ниже) или узнайте, как должен выглядеть интерфейс. -
Теперь вы используете другую структуру данных, которая отображается (в O (1)) метки узла для итераторов очереди. Например, если метки узлов являются (последовательными) целыми числами, вы можете использовать
vectorитераторов; если они в основном что-то еще, вы, вероятно, должны использоватьunordered_map, -
Каждая структура узла также должна включать метку, используемую структурой данных в 2.
Пункт 3. означает, что вам нужно добавить следующее в ваш код выше.
struct node {
...
// Identifies
Label label;
};
Обратите внимание, как это позволяет вам отделить очередь с приоритетами от другой структуры данных. Когда вы делаете decrease_key, и ваш node перемещается в очереди приоритетов, вам не нужно ни о чем беспокоиться, так как каждый узел содержит label член.
Сказав все это, вы также должны рассмотреть возможность использования Boost Graph Library который уже имеет алгоритм Прима.
Другие решения