Приоритет узла алгоритма прим
Итак, мне дали этот псевдокод для алгоритма Примса,
INPUT: GRAPH G = (V,E)
OUTPUT: Minimum spanning tree of G
Select arbitrary vertex s that exists within V
Construct an empty tree mst
Construct an empty priority queue Q that contain nodes ordered by their “distance” from mst
Insert s into Q with priority 0
while there exists a vertex v such that v exists in V and v does not exist in mst do
let v = Q.findMin()
Q.removeMin()
for vertex u that exists in neighbors(v) do
if v does not exist in mst then
if weight(u, v) < Q.getPriority(u) then
//TODO: What goes here?
end if
end if
end for
end while
return mst
Что идет в // ТОДО
Решение
ТОДО это
Q.setPriority(u) = weight(u, v);
кроме того, ваша очередь не работает хорошо. Приоритет узла кроме s должен быть инициализирован как ∞.
как psuedocode, я переписал его ниже:
MST-PRIM(G,w,s)
for each u in G.V
u.priority = ∞
u.p = NULL //u's parent in MST
s.key = 0
Q = G.V // Q is a priority queue
while(Q!=∅)
u = EXTRACT-MIN(Q)
for each v in u's adjacent vertex
if v∈Q and w(u,v) < v.priority
v.p = u
v.priority = w(u,v)
Вы можете найти его прототип в главе 23.2 «Введение в алгоритм».
Другие решения
Других решений пока нет …