Yes 2^{nd} is correct, Prims works similarly to Dijkstra so once the vertex has been relaxed we don’t update the values, so it’s a kind of implicit cycle check.

Awesome q2a theme

0 votes

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)

8,968 questions

3,119 answers

14,341 comments

95,792 users