Проектирование структур данных для реализации Prim в C++

Question

Я пытаюсь реализовать алгоритм Prim для MST в C++. У меня вопрос дизайна

Я реализовал мини-кучу, которая принимает целое число, и мы можем извлечь-мин, уменьшить ключ и вставить ключ.

Теперь, как я понимаю в Prim, мне нужно поддерживать вес, информацию о соседях для каждой вершины. Некоторые идеи у меня есть следующие:

1] Определение структуры

struct node { 
    int vertex; 
    int weight; 
    int neighbor; 
}; 

Используйте мин кучу, чтобы вернуть узел с минимальным весом. Но проблема заключается в уменьшении ключа, так как для клавиши уменьшения вызывающая сторона должна передать вершину, для которой он хочет уменьшить ключ. Поскольку куча меняет элементы слишком часто, я должен пройти весь список, чтобы найти вершину, а затем уменьшить ее ключ. Это O (n), я думаю, что Prim будет хуже, если я это сделаю.

2] Другим способом было бы поддерживать другой массив, который отслеживает положение вершины в очереди с мини-кучей. Но было бы громоздко отслеживать позиции во время операций с минимальными кучами.

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

Answer 1

Вам действительно нужно сделать несколько перекрестных ссылок между структурами данных. Тем не менее, вы пишете

Но было бы громоздким отслеживать позиции в течение мин-кучи операций

, не десть правильно. Используя следующее, вы можете повторно использовать или писать многократно используемые структуры данных, которые этого не требуют.

1. Начнем с того, ваша приоритетная очередь необходимо подвергать какой-то iterator, что позволяет O (1) доступа. Для этого вы можете напрямую использовать boost.Heap (см. Примечание ниже) или получить оттуда идею о том, как должен выглядеть интерфейс.

2. Теперь вы используете другую структуру данных, которая отображает (в O (1)) метки узлов на итераторы очереди. Например, если метки узлов являются (последовательными) целыми числами, вы можете использовать итераторы vector; если они в основном что-то еще, вы, вероятно, должны использовать unordered_map.

3. Каждая структура узла также должна включать в себя метку, используемую структуру данных в 2.

Пункт 3. означает, что вам необходимо добавить следующие строки в коде выше.

struct node { 
    ... 
    // Identifies 
    Label label; 
}; 

Обратите внимание, что это позволяет отделить приоритетную очередь от другой структуры данных. Когда вы делаете decrease_key, а ваш node перемещается в очереди приоритетов, вам не нужно ни о чем беспокоиться, так как каждый узел содержит член label.

---

Сказав все это, вы должны также рассмотреть вопрос просто с помощью Boost Graph Library, который уже имеет алгоритм Прима.