MST-алгоритм Прима в O (| V | ^ 2) - PullRequest
Новая
       34

MST-алгоритм Прима в O (| V | ^ 2)

5 голосов
/ 06 августа 2010

Временная сложность Алгоритм MST Прима равен O(|V|^2), если вы используете представление матрицы смежности.

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

V = {1,2...,n}
U = {1}
T = NULL
while V != U:

     /* 
         Now this implementation means that 
         I find lowest cost edge in O(n).
         How do I do that using adjacency list? 
     */

     let (u, v) be the lowest cost edge 
                such that u is in U and v is in V - U;

     T = T + {(u,v)}
     U = U + {v}

EDIT:

  1. Я очень хорошо понимаю алгоритм Прима.
  2. Я знаю, как эффективно реализовать это, используя кучи и очереди с приоритетами.
  3. Я также знаю о лучших алгоритмах.
  4. Я хочу использовать матричное представление смежности для графа и получить реализацию O (| V | ^ 2).

ХОЧУ НЕПРАВИЛЬНУЮ РЕАЛИЗАЦИЮ

Ответы [ 3 ]

5 голосов
/ 06 августа 2010

Нахождение ребра самой низкой стоимости ( u , v ), так что u находится в U, а v - в VU,выполняется с приоритетной очередью .Точнее говоря, приоритетная очередь содержит каждый узел v из VU вместе с наименьшим ребром стоимости из v в текущее дерево U. Другими словами, очередь содержит точно | VU |elements.

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

Выбор очереди приоритетов определяет сложность времени.Вы получите O (| V | ^ 2), реализовав приоритетную очередь в виде простого массива cheapest_edges[1..|V|].Это потому, что поиск минимума в этой очереди занимает время O (| V |), и вы повторяете, что | V |раз.

В псевдокоде: 

V = {2...,n}
U = {1}
T = NULL
P = array, for each v set P[v] = (1,v)

while V != U

    (u,v) = P[v] with v such that  length P[v]  is minimal

    T = T + {(u,v)}
    U = U + {v}

    for each w adjacent to v
        if length (v,w) < length P[w] then
            P[w] = (v,w)
0 голосов
/ 06 августа 2010

Вы можете отсортировать ребра по стоимости, а затем итерировать ребра в порядке стоимости, и если этот ребро объединяет два отдельных подграфа, используйте это ребро.

У меня есть реализация здесь .Он считывает количество вершин (N), количество ребер (M) и ребер по порядку (A, B, Cost), а затем выводит ребра.Это алгоритм Крускала.

Реализация алгоритма Прима с кучей, использующая тот же вход, может быть найдена здесь .

0 голосов
/ 06 августа 2010

Вы делаете это, как в алгоритме Дейкстры , выбирая узел, который связан с вашим текущим частичным деревом с минимальным краем затрат (который не генерирует цикл). Я думаю, Википедия объясняет Prim лучше, чем тот псевдокод, который у вас есть. Посмотрите и дайте мне знать, если у вас есть еще вопросы.

...