Explaination of prim's algorithm

Question

I have to implement Prim's algorithm using a min-heap based priority queue. If my graph contained the vertices A, B, C, and D with the below undirected adjacency list... [it is sorted as (vertex name, weight to adjacent vertex)]

A -> B,4 -> D,3
B -> A,4 -> C,1 -> D,7
C -> B,1
D -> B,7 -> A,3

Rough Graph:

A-4-B-1-C
|   /
3  7
| /
D

What would the priority queue look like? I have no idea what I should put into it. Should I put everything? Should I put just A B C and D. I have no clue and I would really like an answer.

Answer 1

Prim's: grow the tree by adding the edge of min weight with exactly one end in the tree.
The PQ contains the edges with one end in the tree.
Start with vertex 0 added to tree and add all vertices connected to 0 into the PQ.
DeleteMin() will give you the min weight edge (v, w), you add it to the MST and add all vertices connected to w into the PQ.

is this enough to get you started?
---
so, in your example, the in the first iteration, the MST will contain vertex A, and the PQ will contain the 2 edges going out from A:
A-4-B
A-3-D

Answer 2

Here's prim's algorithm:

Choose a node. 
Mark it as visited.
Place all edges from this node into a priority queue (sorted to give smallest weights first).  
While queue not empty:  
    pop edge from queue
    if both ends are visited, continue
    add this edge to your minimum spanning tree
    add all edges coming out of the node that hasn't been visited to the queue
    mark that node as visited

So to answer your question, you put the edges in from one node.

If you put all of the edges into the priority queue, you've got Kruskal's algorithm, which is also used for minimum spanning trees.

It depends on how you represent your graph as to what the running time is. Adjacency lists make the complexity O(E log E) for Kruskal's and Prim's is O(E log V) unless you use a fibonacci heap, in which case you can achieve O(E + V log V).

Answer 3

You can assign weights to your vertices. Then use priority queue based on these weights. This is a reference from the wiki: http://en.wikipedia.org/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 ≠ ø)
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)
}

Q will be your priority queue. You can use struct to hold the information of the vertices.