неспособный понять алгоритм примитивов

Question

Помогите в понимании примитивов algo pseudocode (как и в coreman и wiki) Prim's algorithm.

MST-PRIM (G, w, r) { 
 
for each u ∈ G.V 
 
u.key = ∞ 
 
u.parent = NIL 
 
r.key = 0 
 
Q = G.V 
 
while (Q ≠ ø) 
 
//1 
 
u = Extract-Min(Q) 
 
for each v ∈ G.Adj[u] 
 
if (v ∈ Q) and w(u,v) < v.key 
 
v.parent = u 
 
v.key = w(u,v)}

я могу понять до 1 или во время цикла, что r.key = 0 обеспечить neighours или adjacents корня сканируется первым, , но, как у уже принадлежит Q (очереди узлов до сих пор не включены в минимальное остовное дерево примитивов) и v также в Q, не поможет в генерации примитивов MST.

также оба coreman и, таким образом вики состояния

1. A = { (v, v.parent) : v ∈ V - {r} - Q }. 
 
2. The vertices already placed into the minimum spanning tree are those in V−Q. 
 
3. For all vertices v ∈ Q, if v.parent ≠ NIL, then v.key < ∞ and v.key is the weight of a light edge

Перед каждой итерации цикла в то время линий 6-11, (v, v.parent), соединяющей V :: к некоторой вершине, уже помещенной в минимальное остовное дерево.

как A является нашим MST, тогда как 1. поможет, поскольку v уже включен в наш MST (как показано v ∈ V - {r} - Q), почему тогда он должен быть включен.

Answer 1

Для той части, которая у вас есть сомнения:

u = Extract-Min(Q) 
for each v ∈ G.Adj[u] 
if (v ∈ Q) and w(u,v) < v.key 
v.parent = u 
v.key = w(u,v) 

«Для каждой вершины V, атрибут v: ключ минимальный вес любого ребра, соединяющего к вершине дерева, по соглашению, ключ = ∞, если такого ребра нет ». (http://en.wikipedia.org/wiki/Prim's_algorithm)

Следовательно, u = Extract-Min (Q) получит вершину с минимальным ключом.

для каждого v ∈ G.Adj [u] найдет всех соседей u.

if (v ∈ Q) и w (u, v) < v.key условие, чтобы исключить цикл и проверить, должен ли путь обновляться.

Затем следующие строки кода обновляют границы соседей.

v.parent = u 
v.key = w(u,v) 

"Перед каждой итерации цикла в то время линий 6-11, 1. А = {(v, v.parent): V ∈ V - {г} - Q}." (http://en.wikipedia.org/wiki/Prim's_algorithm)

Основываясь на приведенном выше предложении, перед циклом while A пуст как Q = GV! После цикла while вы получите A, содержащий все вершины, которые образуют MST. Каждая вершина v из A имеет родительский элемент (v.parent). Для корня r его родителем является NIL. Корень r исключается из-за утверждения V - {r}, но он существует в A благодаря его дочерним элементам в виде v.parent.

Следовательно, в этой связи http://en.wikipedia.org/wiki/Prim's_algorithm указано, что: «2. Вершины, уже помещенные в минимальное остовное дерево, это те, что находятся в V-Q».

и «Когда алгоритм завершается, очередь с минимальным приоритетом Q пуста, поэтому минимальное связующее дерево A для G равно A = {(v, v.parent): v ∈ V - {r}}".