Shouldn’t the second condition in line 40 be written as
if(visited[neighbour]==true && parent[neighbour]!=node)
Change in second condition in line 40
Hello @Jalaanchal-Tewari-1816244721737412,
No, it is written correct in the video.
Let’s understand, why?
- Your are returning true if the node has already been visited, which indicates presence of cycle.
2… As you know, the neighbour of a node includes it parent also.
Example: for node being 1,
parent=0
neighbours=[0,2]
0 has already visited, this can lead to wrong detection of cycle.
Thus, to prevent this condition, we used the condition:
parent[node]!=neighbour
Explanation:
parent[1]!=0 : false
So, the above problem has been solved.
Now, consider what you are saying:
parent[neighbour]!=node:
parent[0]!=1: true and also 0 has visited before.
So, it will return true , causing wrong detection of cycle.
Hope, this would help.
Give a like, if you are satisfied.