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