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

From Традиция
Jump to navigation Jump to search

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

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

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

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

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

Трассировка алгоритма[edit | edit source]

Итерация 1[edit | edit source]

G 0 NY 1 Moscow ($15) 0--1 $60 3 Berlin ($20) 0--3 $50 4 Kiev ($15) 0--4 $80 2 Minsk Start 1--2 $15 1--3 $50 1--4 $10 2--3 $20 2--4 $15 3--4 $30

Итерация 2[edit | edit source]

G 0 NY ($60) 1 Moscow 0--1 $60 3 Berlin ($20) 0--3 $50 4 Kiev ($10) 0--4 $80 2 Minsk Start 1--2 $15 1--3 $50 1--4 $10 2--3 $20 2--4 $15 3--4 $30

Итерация 3[edit | edit source]

G 0 NY ($60) 1 Moscow 0--1 $60 3 Berlin ($20) 0--3 $50 4 Kiev 0--4 $80 2 Minsk Start 1--2 $15 1--3 $50 1--4 $10 2--3 $20 2--4 $15 3--4 $30

Итерация 4[edit | edit source]

G 0 NY ($50) 1 Moscow 0--1 $60 3 Berlin 0--3 $50 4 Kiev 0--4 $80 2 Minsk Start 1--2 $15 1--3 $50 1--4 $10 2--3 $20 2--4 $15 3--4 $30

Итерация 5[edit | edit source]

G 0 NY 1 Moscow 0--1 $60 3 Berlin 0--3 $50 4 Kiev 0--4 $80 2 Minsk Start 1--2 $15 1--3 $50 1--4 $10 2--3 $20 2--4 $15 3--4 $30
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.