In the lecture it is told that we need to start a bfs from every single node. But I don’t understand why is that?..I mean if you start a bfs from any point and encounter a backedge…you can trace back the length of the cycle right there…and every cycle can be measured in this way…so why to start a bfs again & again?
Regarding finding the shortest cycle
@sudhanshujaisani38 hey it may be case that graph is not connected,so two separate components of graphs are there so there may be case that shortest cycle may be in first component or second component so start bfs from each node so that all cases can be consider.
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.
I understood that the cycle may be present in the other connected component but in that case we should run one bfs for one component right? because we can detect every cycle in one single component whenever a backedge is encountered right? (which is different from running bfs from every single node in the same connected component, and in fact in this case, we would be encountering same cycle again & again)
@sudhanshujaisani38 hey uske lie apko connected components dhundne pdenge than apko har component pr bfs lgani pdegi to kam badh jayega thats why hmne hr ek node pr lgayi.
I don’t feel ki kaam badh Jayega? The same loop you’re running to start the bfs from every node will do the job if a check is added for starting the bfs only from unvisited nodes. I’m just asking is that will there be a case where my approach will give wrong answer?