Как сравнить узлы в minHeapify для минимального связующего дерева?
Я пытаюсь создать минимальное связующее дерево, используя алгоритм prim, и у меня есть главный вопрос о реальной куче. Я структурировал свой список смежности графов как вектор вершин, и у каждой вершины есть вектор ребер. Ребра содержат вес, соединительную вершину и ключ. Я не уверен, должна ли моя куча быть кучей вершин или ребер. Если я сделаю это кучей вершин, то нет никакого способа определить, идут ли веса от одной и той же родительской и конечной вершин, что заставляет меня думать, что я должен создать кучу для каждого списка вершин ребер. Итак, мой последний вопрос: я должен создать кучу ребер или кучу вершин? Если это список ребер, должен ли я использовать вес на ребрах в качестве ключа или у меня должен быть отдельный элемент данных под названием ключ, который я могу фактически использовать для очереди приоритетов? Спасибо!
Решение
Вы должны сделать minHeap ребер, так как вы собираетесь сортировать ребра по их весу но ребра должны содержать две вершины: представляющие одну вершину на каждом конце. В противном случае, как вы предложили: нет способа определить, идут ли веса от одной и той же родительской и конечной вершин. Поэтому вы должны реструктурировать свой реберный класс и сделать из него minHeap.
Рассмотрим алгоритм из Wiki также.
Инициализировать дерево с одной выбранной вершиной
произвольно из графика.Расти дерево одним краем: из краев
которые соединяют дерево с вершинами, которых еще нет в дереве, найдите
минимальный вес ребра, и перенести его на дерево.Повторите шаг 2 (пока все вершины в дереве).
Я не полностью понимаю ключевое поле в пограничном классе. Я предполагаю, что это как Id к краю. Таким образом, вы должны создать кучу из них, но так как вы предоставляете пользовательскую структуру данных для кучи, вы также должны предоставить функцию сравнения для класса ребер, то есть определить bool operator<(const Edge&) метод.
Другие решения
Ваша куча может быть из пар <vertex, weight>и будет содержать вершины, которые находятся на расстоянии одного ребра от любой вершины, уже находящейся в частичном минимальном остовном дереве. (редактировать: в некоторых случаях он может содержать вершину, которая уже находится в частичном 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.
Замечания: Встроенная функция здесь вам не поможет, поэтому вам нужно создать собственную кучу, чтобы эта работа работала эффективно. Инициализируйте значения ключа каждой вершины до некоторого бесконечного значения в начале
Другой подход: Сохраните все ребра, которые указывают на непосещенную вершину с весом в минимальной куче. Но это потребовало бы более высокой пространственной сложности, чем другой подход, но имеет аналогичную амортизированную временную сложность. Когда вы извлекаете ребро, проверьте, посещена ли вершина, на которую он указывает, или нет, если вы посещаете, извлеките ребро еще раз и отбросьте ребро.