Алгоритм Прима — различия между версиями
Материал из CustisWiki
(не показана 1 промежуточная версия 1 участника) Строка 14:
Строка 14: <code-python>
<code-python>
− def mst_prim(G,s):
+ # Находит минимальное остовное дерево
− # минимальное остовное дерево, хэш (вершина:предшествующая вершина)
+ # в графе $G$, со стартовой вершиной $s$
+ def mst_prim(G,s):
+ print "StartVertice:",s
+ # минимальное остовное дерево в виде хэш-таблицы (вершина:предшествующая вершина)
MST={}
MST={}
− # хэш, граничащих с MST, узел:(стоимость)
+ ToVisit={s:0} # хэш-таблица вершин , граничащих с MST, узел:(стоимость)
− ToVisit={s:0}
+ Predecessor ={s:s } # хэш, содержащий вершины из которых планируется включать другие вершины.
− # хэш: вершины из которых планируется включать другие вершины.
+ while ToVisit : # пока есть вершины, до которых не построен кратчайший путь
− Predecessor={s:s}
+ print MST, ToVisit, "-------->",
− # пока есть вершины, до которых не построен кратчайший путь
+ v=argmin(ToVisit) # выбираем ближайшую достижимую вершину
− while ToVisit:
+
− # выбираем ближайшую достижимую вершину
+
− v=argmin(ToVisit)
+
MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];
MST[v]=Predecessor[v]; del ToVisit[v]; del Predecessor[v];
− # для всех соседей вершины $v$
+ for w in G.neighbors(v): # для всех соседей вершины $v$
− for w in G.neighbors(v):
+ if (w not in MST): # которые еще не в нашем остовном дереве
− # которые еще не в нашем остовном дереве
+
− if (w not in MST):
+
# обновляем стоимость включения в MST
# обновляем стоимость включения в MST
if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]):
if (w not in ToVisit) or (G.get_edge(v,w) < ToVisit[w]):
ToVisit[w] = G.get_edge(v,w)
ToVisit[w] = G.get_edge(v,w)
Predecessor[w] = v
Predecessor[w] = v
− print_frame(G, MST, ToVisit, Predecessor)
+ print MST, ToVisit, Predecessor
+ print MST
return MST
return MST
</code-python>
</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}
− ===Итерация 1===
+ <graph >
− <neato>
+ graph G{ rankdir=TB;
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
+ 0 [label="NY(0) "];
− edge[len=3,fontcolor="blue",style="dashed"];
+ 1 [label="Moscow(1 )"];
− node[fontcolor="red"];
+ 2 [label="Minsk(2) "];
−
+ 3 [label="Berlin(3 )"];
−
+ 4 [label="Kiev(4 )"];
− 0 [label="NY", ];
+ 0 -- 1[fontcolor="blue", label="$60",style=solid ];
−
+ 0 -- 3[fontcolor="blue", label="$50",style=bold ];
− 1 [label="Moscow ($15)", style=filled, fillcolor="yellow" ];
+ 0 -- 4[fontcolor="blue", label="$80",style=solid ];
−
+ 1 -- 2[fontcolor="blue", label="$15",style=bold ];
− 2 [label="Minsk\n Start", shape=box, periferies=2 ];
+ 1 -- 3[fontcolor="blue", label="$50",style=solid ];
−
+ 1 -- 4[fontcolor="blue", label="$10",style=bold ];
− 3 [label="Berlin ($20)", style=filled, fillcolor="yellow" ];
+ 2 -- 3[fontcolor="blue", label="$20",style=bold ];
−
+ 2 -- 4[fontcolor="blue", label="$15",style=solid ];
− 4 [label="Kiev ($15)", style=filled, fillcolor="yellow" ];
+ 3 -- 4[fontcolor="blue", label="$30",style=solid ];
−
+ }
−
+ </graph >
− 0 -- 1 [label="$60", ];
+
−
+
− 0 -- 3 [label="$50", ];
+
−
+
− 0 -- 4 [label="$80", ];
+
−
+
− 1 -- 2 [label="$15", ];
+
−
+
− 1 -- 3 [label="$50", ];
+
−
+
− 1 -- 4 [label="$10", ];
+
−
+
− 2 -- 3 [label="$20", ];
+
−
+
− 2 -- 4 [label="$15", ];
+
−
+
− 3 -- 4 [label="$30", ];
+
−
+
− }
+
− </neato>
+
− ===Итерация 2===
− <neato>
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
− edge[len=3,fontcolor="blue",style="dashed"];
− node[fontcolor="red"];
−
−
− 0 [label="NY ($60)", style=filled, fillcolor="yellow" ];
−
− 1 [label="Moscow", ];
−
− 2 [label="Minsk\n Start", shape=box, periferies=2 ];
−
− 3 [label="Berlin ($20)", style=filled, fillcolor="yellow" ];
−
− 4 [label="Kiev ($10)", style=filled, fillcolor="yellow" ];
−
−
− 0 -- 1 [label="$60", ];
−
− 0 -- 3 [label="$50", ];
−
− 0 -- 4 [label="$80", ];
−
− 1 -- 2 [label="$15", style=bold ];
−
− 1 -- 3 [label="$50", ];
−
− 1 -- 4 [label="$10", ];
−
− 2 -- 3 [label="$20", ];
−
− 2 -- 4 [label="$15", ];
−
− 3 -- 4 [label="$30", ];
−
− }
− </neato>
− ===Итерация 3===
+ [[Category:Алгоритмы]]
− <neato>
+
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
+
− edge[len=3,fontcolor="blue",style="dashed"];
+
− node[fontcolor="red"];
+
−
+
−
+
− 0 [label="NY ($60)", style=filled, fillcolor="yellow" ];
+
−
+
− 1 [label="Moscow", ];
+
−
+
− 2 [label="Minsk\n Start", shape=box, periferies=2 ];
+
−
+
− 3 [label="Berlin ($20)", style=filled, fillcolor="yellow" ];
+
−
+
− 4 [label="Kiev", ];
+
−
+
−
+
− 0 -- 1 [label="$60", ];
+
−
+
− 0 -- 3 [label="$50", ];
+
−
+
− 0 -- 4 [label="$80", ];
+
−
+
− 1 -- 2 [label="$15", style=bold ];
+
−
+
− 1 -- 3 [label="$50", ];
+
−
+
− 1 -- 4 [label="$10", style=bold ];
+
−
+
− 2 -- 3 [label="$20", ];
+
−
+
− 2 -- 4 [label="$15", ];
+
−
+
− 3 -- 4 [label="$30", ];
+
−
+
− }
+
− </neato>
+
−
+
− ===Итерация 4===
+
− <neato>
+
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
+
− edge[len=3,fontcolor="blue",style="dashed"];
+
− node[fontcolor="red"];
+
−
+
−
+
− 0 [label="NY ($50)", style=filled, fillcolor="yellow" ];
+
−
+
− 1 [label="Moscow", ];
+
−
+
− 2 [label="Minsk\n Start", shape=box, periferies=2 ];
+
−
+
− 3 [label="Berlin", ];
+
−
+
− 4 [label="Kiev", ];
+
−
+
−
+
− 0 -- 1 [label="$60", ];
+
−
+
− 0 -- 3 [label="$50", ];
+
−
+
− 0 -- 4 [label="$80", ];
+
−
+
− 1 -- 2 [label="$15", style=bold ];
+
−
+
− 1 -- 3 [label="$50", ];
+
−
+
− 1 -- 4 [label="$10", style=bold ];
+
−
+
− 2 -- 3 [label="$20", style=bold ];
+
−
+
− 2 -- 4 [label="$15", ];
+
−
+
− 3 -- 4 [label="$30", ];
+
−
+
− }
+
− </neato>
+
−
+
− ===Итерация 5===
+
− <neato>
+
− graph G{ rankdir=LR; overlap=scale; rankdir=TB; splines=true;
+
− edge[len=3,fontcolor="blue",style="dashed"];
+
− node[fontcolor="red"];
+
−
+
−
+
− 0 [label="NY", ];
+
−
+
− 1 [label="Moscow", ];
+
−
+
− 2 [label="Minsk\n Start", shape=box, periferies=2 ];
+
−
+
− 3 [label="Berlin", ];
+
−
+
− 4 [label="Kiev", ];
+
−
+
−
+
− 0 -- 1 [label="$60", ];
+
−
+
− 0 -- 3 [label="$50", style=bold ];
+
−
+
− 0 -- 4 [label="$80", ];
+
−
+
− 1 -- 2 [label="$15", style=bold ];
+
−
+
− 1 -- 3 [label="$50", ];
+
−
+
− 1 -- 4 [label="$10", style=bold ];
+
−
+
− 2 -- 3 [label="$20", style=bold ];
+
−
+
− 2 -- 4 [label="$15", ];
+
−
+
− 3 -- 4 [label="$30", ];
+
−
+
− }
+
− </neato>
+
−
+
−
+
− [[Category:Алгоритмы|П]]
+
{{replicate-from-custiswiki-to-lib}}
{{replicate-from-custiswiki-to-lib}}
Версия 07:40, 6 декабря 2005
Алгоритм Прима предназначен для решения задачи
Минимальное остовное дерево .
В этом алгоритме минимальный остов строится постепенно: сначала выбирается произвольная
вершина, которая включается в остов, затем, на каждой итерации, к
текущему остову добавляется наиболее дешевое ребро (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}
[svg]
