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])