In BFS traversal How can we know that there is a cycle if dist[neigh] >= dist[curr]
Check Cycle in Undirected graph using Distance array
hello @bugfreecoder
we are at current node and we found that one of the neighbour is already visited .
now for cycle to exist this node should not be a parent node of current node.
now ur task is to check whether neighbour is parent of not.
how we will do that?
see if negighbour is parent then dist[curr] will always be 1 + distance[parent] right? i.e dist[cur] > dis[parent]
so if condition dist[cur] > dist[neighbour] not holds that means neighbour is not parent hence
there is cycle .
so we can say if dist[cur] <=dis[neighbour] then there is cycle because that neighbour is not parent
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.