Do we need cycle checking algorithm for both Kruskal’s and Prim’s algorithm ?
Arguably, on a directed graph, we need one for sure with both algorithms. But for undirected weighted graph, we may have 2 opinions as follows :
- Cycle checking will be required for Kruskal’s but not for Prim’s because Prim’s always chooses the closest unvisited vertex to the current tree
- Cycle checking will be required for BOTH Kruskal’s and Prim’s. Kruskal’s algorithm will be an explicit cycle checking algorithm. Whereas Prim’s implicitly checks for cycles when selecting the new vertex
Which of these opinions is correct / more accurate ?
I am personally tending towards second opinion (both algorithms have a need of cycle checking algorithm)