Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

So I was given this psuedocode for Prims-Algorithm, 

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

What goes in the //TODO

share|improve this question

1 Answer

up vote 1 down vote accepted

TODO is

Q.setPriority(u) = weight(u, v);

besides, your queue don't work well. The priority of a node except s should be initialize as ∞.

as psuedocode, I rewrited it below:

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)

You can find its prototype in chapter23.2 of Introduce to Algorithm.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.