|
|
| (не показано 5 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | Алгоритм Прима предназначен для решения задачи
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | [[Минимальное остовное дерево]].
| + | |
| − | | + | |
| − | В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная
| + | |
| − | вершина, которая включается в остов, затем, на каждой итерации, к
| + | |
| − | текущему остову добавляется наиболее дешевое ребро ''(u,v)'',
| + | |
| − | соединяющее какую-либо вершину из остова ''u'', с какой-либо
| + | |
| − | вершиной ''v'' не из остова.
| + | |
| − | Алгоритм Прима, похож на [[алгоритм Дейкстры]], он также является жадным алгоритмом.
| + | |
| − | | + | |
| − | Код алгоритма, представлен в виде функции на языке [[Python]].
| + | |
| − | | + | |
| − | Сложность алгоритма равна <math>O(n^3)</math>.
| + | |
| − | | + | |
| − | <code-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
| + | |
| − | </code-python>
| + | |
| − | | + | |
| − | 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}
| + | |
| − | | + | |
| − | <graph>
| + | |
| − | graph G{ rankdir=TB;
| + | |
| − | 0 [label="NY(0)"];
| + | |
| − | 1 [label="Moscow(1)"];
| + | |
| − | 2 [label="Minsk(2)"];
| + | |
| − | 3 [label="Berlin(3)"];
| + | |
| − | 4 [label="Kiev(4)"];
| + | |
| − | 0 -- 1[fontcolor="blue",label="$60",style=solid];
| + | |
| − | 0 -- 3[fontcolor="blue",label="$50",style=bold];
| + | |
| − | 0 -- 4[fontcolor="blue",label="$80",style=solid];
| + | |
| − | 1 -- 2[fontcolor="blue",label="$15",style=bold];
| + | |
| − | 1 -- 3[fontcolor="blue",label="$50",style=solid];
| + | |
| − | 1 -- 4[fontcolor="blue",label="$10",style=bold];
| + | |
| − | 2 -- 3[fontcolor="blue",label="$20",style=bold];
| + | |
| − | 2 -- 4[fontcolor="blue",label="$15",style=solid];
| + | |
| − | 3 -- 4[fontcolor="blue",label="$30",style=solid];
| + | |
| − | }
| + | |
| − | </graph>
| + | |
| − | | + | |
| − | | + | |
| − | [[Category:Алгоритмы]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
