Я пытаюсь создать минимальное связующее дерево, используя алгоритм prim, и у меня есть главный вопрос о фактической куче. Я структурировал список смежности графиков как вектор вершин, и каждая вершина имеет вектор ребер. Края содержат вес, соединительную вершину и ключ. Я не уверен, должна ли моя куча быть кучей вершин или краев. Если я сделаю это кучей вершин, тогда нет способа определить, идут ли веса из одной и той же родительской и целевой вершин, что заставляет меня думать, что я должен делать кучу для каждого списка ребер. Итак, мой последний вопрос - создать кучу ребер или кучу вершин? Если его список ребер, я должен использовать вес по краям в качестве ключа, или я должен иметь отдельный элемент данных, называемый ключом, который я могу фактически использовать для очереди приоритетов? Благодаря!Как сравнить узлы в minHeapify для минимального остовного дерева?
ответ
Вы должны сделать minHeap ребер, так как вы собираетесь сортировать ребра по их весу , но ребра должны содержать две вершины: одну вершину на каждом конце. В противном случае, как вы предположили: нет способа определить, идут ли веса из одной и той же родительской и целевой вершины. Поэтому вы должны переструктурировать свой класс edge и сделать minHeap из них.
Рассмотрите алгоритм от Wiki.
Инициализировать дерево с помощью одной вершины, выбрал произвольно с графика.
Выращивание дерева одним краем: из ребер , которые соединяют дерево с вершинами еще не в дереве, найдите край минимального веса и перенесите его на дерево.
Повторите шаг 2 (пока все вершины не находятся в дереве).
Я не совсем понимаю ключевое поле в классе кромок. Я предполагаю, что это похоже на Id. Поэтому вы должны сделать кучу, но поскольку вы предоставляете определенную пользователем структуру данных в кучу, вы также должны предоставить функцию сравнения для класса edge, т. Е. Определить метод bool operator<(const Edge&).
Ваша куча может быть из пар <vertex, weight> и будет содержать вершины, которые являются одним краем от любой вершины, уже находящейся в частичном минимальном остовном дереве. (edit: в некоторых случаях он может содержать вершину, которая уже находится в частичном MST, вы должны игнорировать такие элементы, когда они выходят).
Это может быть куча ребер, как <src, dst, weight>, что практически то же самое, вы просто игнорировать src пока dst такая же, как vertex в первом варианте.
PS. Относительно этого key вещь, я не вижу необходимости в каких-либо ключах, вам нужно сравнить веса.
Куча должна поддерживать вершины с ключом как наименьший взвешенный край. Поскольку вершина все еще не посещена, то любое ребро к ней не будет выбрано, поэтому минимум всего нераскрытого края для невидимой вершины будет следующим краем, которое будет добавлено к обложке, поэтому вы удаляете соответствующую ему вершину. Единственная проблема здесь состоит в том, чтобы поддерживать обновленные веса до минимальных ребер до вершины в куче, поскольку связующее дерево изменяется на каждой итерации, а новые кромки добавляются к нему. Способ сделать это состоит в том, чтобы сохранить положение каждой невидимой вершины в куче, когда новая вершина добавляется в остовное дерево, невидимые края из нее обновляются с использованием прямой позиции вершины, на которую они указывают на использование сохраненных позиций. Затем вы обновляете минимальную стоимость вершины, если текущая стоимость меньше, чем новый вес края.Затем высушите его кучей, используя стандартную процедуру кучи для поддержания минимальной кучи.
структура данные: -
<Vertex,Weight> : Vertex id & weight of minimum edge to it as record of heap
position[Vertex] : The position of vertex record in heap.
Примечания: встроенная функция не помогут вам здесь, следовательно, вы должны построить свою собственную кучу, чтобы сделать эту работу efficiently.Initialize ключевых значений для каждой вершины в некоторую бесконечную ценность в начало
Другой подход: Сохраните все края, которые указывают на невидимую вершину с массой в куче. Но для этого потребуется более высокая космическая сложность, чем другой подход, но с аналогичной амортизированной временной сложностью. Когда вы извлекаете реберную проверку, если вершина, на которую он указывает, посещается или нет, если вы снова посещаете извлечение и отбрасываете край.