This is a discussion on Vague understanding about Prim's within the C++ Programming forums, part of the General Programming Boards category; Hi, It is very clear how Kruskal algorithm prevents a cycle when finding the minimum spanning tree. Weird thing is ...

1. ## Vague understanding about Prim's

Hi,
It is very clear how Kruskal algorithm prevents a cycle when finding the minimum spanning tree.
Weird thing is I have implemented Prims algorithm, but I can't tell for the life of me what actually chooses a unique edge.
I think it is due to the fact that we check if a node has not been inserted into the heap. So all the nodes in the heap are open nodes, but the if they're part of the MST we close the node by marking it as visited.
So we only insert once into the heap.
Can anyone clarify this..I was just writing the report and I was like..hold on..W*F?

Code:
```     if(u not in heap)
pq.insert(u) //does the line prevent a cycle forming? pq is a priority queue
else
siftup(hpos[u])```

2. I'm not sure if it's going to make sense when I put it like this, but if a node is already in the MST, a circular graph should be impossible because it is either the child of some other node, or it is a parent of some other node. If it is a parent, it will be connected by a vertex on the same level as another node that is of equal or less weight (which is why you sift up existing nodes).

3. I think I understand what you're saying..
I was thinking I insert into the heap once because if we don't we risk visiting a node twice.
If a node is already part of the MST, but another node connected happens to have a lesser distance..if we do not do a check it will insert the visited node, change its parent to be incorrect..and at some later point pop the visited node out again. Which is wrong, as that forms a cycle.
I had to step through the algorithm again..not sure?

4. Wait I'm being confusing... yes, you understand now.

It's not that we are afraid of visiting the node twice in the algorithm, because every vertex will be tested.

But if you did insert a node twice, it would be wrong, since that forms a cycle somewhere in the graph (the same node was copied into the MST twice and now has two different parents).

5. Thank you man..now I can continue with this darn report