Cycle detection in Prim's Algorithm

Question

Why don't we check for the cycle in prim's algorithm like in Kruskal's algorithm to find the minimum spanning tree?

Answer 1

That depends on your definition of finding cycles.

The critical part of Prims's is to find the shortest edge from A to a none-A vertex, to be able to do that we need to remove edges that are internal to A, ie. cycles, to get the shortest external.

In Kruskal, we need to remove edges that internal to any A.

So in reality its the same.

Answer 2

In Prim's algorithm

Each step adds to the tree A a light edge that connects A to an isolated vertex—one on which no edge of A is incident.

Source: page 634 of CLRS.

So we don't need to detect cycles while forming the minimum spanning tree like we do in Kruskal’s Algorithm using a disjoint set data structure.

Answer 3

That's just how the algorithm works. The algorithm itself checks for cycles. Prim's algorithm uses a sort of union-find and using union-find, you can't add the same vertex more than once.