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

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

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

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

Сложность алгоритма равна .

 # Находит минимальное остовное дерево 
 # в графе $G$, со стартовой вершиной $s$
 def mst_prim(G,s):
    print "StartVertice:",s
    # минимальное остовное дерево в виде хэш-таблицы (вершина:предшествующая вершина)
    MST={}                  
    ToVisit={s:0}     # хэш-таблица вершин, граничащих с MST, узел:(стоимость)
    Predecessor={s:s} # хэш, содержащий вершины из которых планируется включать другие вершины. 
    while ToVisit:  # пока есть вершины, до которых не построен кратчайший путь
        print MST, ToVisit, "-------->",
        v=argmin(ToVisit)       # выбираем ближайшую достижимую вершину
        MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];   
        for w in G.neighbors(v): # для всех соседей вершины $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 MST, ToVisit, Predecessor
    print MST
    return MST

StartVertice: 2
{} {2: 0} --------> {2: 2} {1: 15, 3: 20, 4: 15} {1: 2, 3: 2, 4: 2}
{2: 2} {1: 15, 3: 20, 4: 15} --------> {1: 2, 2: 2} {0: 60, 3: 20, 4: 10} {0: 1, 3: 2, 4: 1}
{1: 2, 2: 2} {0: 60, 3: 20, 4: 10} --------> {1: 2, 2: 2, 4: 1} {0: 60, 3: 20} {0: 1, 3: 2}
{1: 2, 2: 2, 4: 1} {0: 60, 3: 20} --------> {1: 2, 2: 2, 3: 2, 4: 1} {0: 50} {0: 3}
{1: 2, 2: 2, 3: 2, 4: 1} {0: 50} --------> {0: 3, 1: 2, 2: 2, 3: 2, 4: 1} {} {}
{0: 3, 1: 2, 2: 2, 3: 2, 4: 1}

---

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Алгоритм Прима»