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 :

  1. 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
  2. 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)

ago in Algorithms by (5 points) | 12 views

Yes 2nd 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.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,968 questions
3,119 answers
95,792 users