Алгоритм Прима

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Алгоритм Прима предназначен для решения задачи Минимальное остовное дерево.

В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная вершина, которая включается в остов, затем, на каждой итерации, к текущему остову добавляется наиболее дешевое ребро (u, v), соединяющее какую-либо вершину из остова u, с какой-либо вершиной v не из остова. Алгоритм Прима, похож на алгоритм Дейкстры, он также является жадным алгоритмом.

Код алгоритма, представлен в виде функции на языке Python.

Сложность алгоритма равна \(O(n^3)\).

<code-python> def mst_prim(G,s):

   # минимальное остовное дерево, хэш (вершина:предшествующая вершина)
   MST={}                  
   # хэш, граничащих с MST, узел:(стоимость)
   ToVisit={s:0}     
   # хэш: вершины из которых планируется включать другие вершины. 
   Predecessor={s:s} 
   # пока есть вершины, до которых не построен кратчайший путь
   while ToVisit:  
       # выбираем ближайшую достижимую вершину
       v=argmin(ToVisit)       
       MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];   
       # для всех соседей вершины $v$
       for w in G.neighbors(v):
           # которые еще не в нашем остовном дереве      
           if (w not in MST):  
               # обновляем стоимость включения в MST
               if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]):
                   ToVisit[w] = G.get_edge(v,w)
                   Predecessor[w] = v
       print_frame(G, MST, ToVisit, Predecessor)                
   return MST

</code-python>

Трассировка алгоритма[править]

Итерация 1[править]

Graph image creation requires permission to upload.

Итерация 2[править]

Graph image creation requires permission to upload.

Итерация 3[править]

Graph image creation requires permission to upload.

Итерация 4[править]

Graph image creation requires permission to upload.

Итерация 5[править]

Graph image creation requires permission to upload.


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.