Алгоритм Прима — различия между версиями

Версия 07:53, 6 марта 2007

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

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

Код алгоритма, представлен в виде функции на языке 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

Трассировка алгоритма

Итерация 1

Итерация 2

Итерация 3

Итерация 4

Итерация 5