CODEWITHSUNDEEP
algorithmgraph-theoryprims-algorithm
MikeTheTall
MikeTheTall

Reputation: 3583

Error in Wikipedia pseudocode for Prim's Algorithm?

So I'm looking at the Wikipedia entry on Prim's algorithm:

1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that cheapest connection). To initialize these values, set all values of C[v] to +∞ (or to any number larger than the maximum edge weight) and set each E[v] to a special flag value indicating that there is no edge connecting v to earlier vertices.
2. Initialize an empty forest F and a set Q of vertices that have not yet been included in F (initially, all vertices).
3. Repeat the following steps until Q is empty:
      a. Find and remove a vertex v from Q having the minimum possible value of C[v]
      b. Add v to F
      c. Loop over the edges vw connecting v to other vertices w. For each such edge, if w still belongs to Q and vw has smaller weight than C[w], perform the following steps:
            i. Set C[w] to the cost of edge vw
            ii. Set E[w] to point to edge vw.
4. Return F

My question is about step 3.b ("Add v to F"). Is step 3b an error? "v" is a vertex and the Minimum Spanning Tree is a set of edges (not a set of vertices).

It seems like step 3b ought to read "Add E[v] to F" instead.

Upvotes: 1

Views: 88

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

Step 3b adds vertex v to F. Steps ci and cii then add edges to F

Upvotes: 0

Related Questions