Зачем нам приоритетная очередь в алгоритме Прима - PullRequest
Новая
       48

Зачем нам приоритетная очередь в алгоритме Прима

4 голосов
/ 12 августа 2011

Поскольку мой вопрос говорит, я хочу знать, почему мы используем приоритетную очередь в Алгоритме Прима ?Как это спасает нас от использования наивного пути (да, я слышал об этом, но не знаю почему).

Я был бы очень рад, если бы кто-нибудь мог объяснить шаг за шагом список смежности.Я использую книгу Кормена.

Псевдокод: 

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ← ∞ // what is key?
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

Я думаю использовать std :: vector then std :: make_heap ();в качестве приоритетной очереди для хранения ребер.

Ответы [ 4 ]

10 голосов
/ 12 августа 2011

В алгоритме Прима есть шаг, где вы должны получить «ближайшую» вершину.Этот шаг будет стоить O (N) при использовании обычного массива, но потребуется только O (logN), если вы используете приоритетную очередь (например, кучу)

Следовательно, причина использования приоритетной очереди состоит в том, чтобы уменьшитьвременная сложность алгоритма (что означает, что ваша программа работает быстрее)

**

Обновление:

**

Вот описание алгоритма Прима из Wikipedia .Жирная часть - это часть для нахождения ближайшей вершины, о которой я говорил:

Входные данные: непустой связный взвешенный граф с вершинами V и ребрами E (веса могут быть отрицательными).

Initialize: Vnew = {x}, где x - произвольный узел (начальная точка) из V, Enew = {}

Повторяется до Vnew = V: Выберите ребро (u, v) с минимальным весомтакой, что u находится в Vnew, а v не (если есть несколько ребер с одинаковым весом, можно выбрать любой из них) Добавьте v к Vnew и (u, v) к Enew

Вывод: Vnew и Enew описывают минимальное связующее дерево

6 голосов
/ 12 августа 2011

Вам это не «нужно». Фактически, наивная реализация алгоритма Прима будет просто выполнять линейный поиск по массиву расстояний, чтобы найти следующую ближайшую вершину. Алгоритм Дейкстры работает точно так же.

Причина, по которой люди используют , заключается в том, что это значительно ускоряет время выполнения алгоритма. Получается от O(V^2 + E) до O(E*log(V)).

Ключом к этому является функция EXTRACT-MIN(Q). Если вы сделаете это наивно, эта операция займет время O(V). С кучей, это займет всего O(logV) раз.

3 голосов
/ 15 августа 2011

Делая это примерно из памяти, так что это может быть немного противоречивым, но оно дает понять: 

class Graph
  Set<node> nodes;   // The set of nodes in the graph
  MultiMap<Node, Edge> edges; // Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree.

Graph Prim(Graph input):
   Graph MST = new Graph();
   PriorityQueue<Edge> candidateEdges;
   Node anyNode = input.pickAnyNodeAtRandom()
   candidateEdges.putAll(input.edges.get(anyNode));

   while MST.nodes.size() < input.nodes.size():
      edge = candidateEdges.takeLowest()  // THIS IS THE IMPORTANT PART         
      if edge.v1 in MST.nodes and edge.v2 not in MST.nodes:
         MST.nodes.add(edge.v2)       
         MST.edges.add(edge)
         candidateEdges.add(edge.v2.edges)

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

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

1 голос
/ 28 июня 2013

Алгоритм Прима использует два набора - скажем, U и V / U.

Вы начинаете с корня (корень - единственный элемент в U). Вы помещаете все смежные с ним вершины в очередь с весом [v] = dist [root, v], где v смежен с корнем. Таким образом, когда вы высовываетесь из очереди, вы берете вершину (скажем, u), у которой один конец в U и конец в V / U и наименьший с этим свойством. Вы устанавливаете его вес, его родителя как root и т. Д. И помещаете все его соседние узлы в очередь. Таким образом, теперь очередь имеет все узлы, соседние с корнем, и все узлы, соседние с корнем, и все узлы, смежные с вами, с их соответствующими весами. Таким образом, когда вы откроете его, вы снова получите узел из V / U, который «ближе всего» к U. В реализации они изначально добавляют каждую вершину в очередь с приоритетом INFINITY, но, как вы можете видеть, они постепенно обновляют веса. Это отражается и в приоритетной очереди, гарантируя текст выше.

Надеюсь, это поможет.

...