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

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

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

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:

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

Я ХОЧУ неэффективного ВНЕДРЕНИЕ

источник

2010-08-06 Pratik Deoghare

Вот реализация V^2 в конце страницы http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm – Ankush

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

источник

2010-08-06 10:21:26 IVlad

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

Нахождения самой низкой стоимости кромки (у, против), таким образом, что у в U и V в V-U, делаются с приоритетной очередью а. Точнее, очередь приоритетов содержит каждый узел v из V-U вместе с наименьшим ценовым краем от v в текущее дерево U. Иными словами, очередь содержит точно | V-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)

источник

2010-08-06 11:59:31

Можете ли вы написать небольшой псевдокод? –

Несомненно. Отредактировал мой ответ. –

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

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

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

источник

2010-08-06 13:50:25

ответ

Смежные вопросы