Applications of BFS and DFS

[@anuragbose2622]

Thank you very much for these applications. It helped me solve many questions .

[@nitinat3590]

Brilliant Stuff! Thanks a lot for sharing.

[@ananyakashyap4759]

Very Informative. Thanks

[@VinayRachapalli]

is minimum no.of edges to be removed to make a graph acyclic is no.of back edges??

[@MultiAbhishek1997]

@14:00 he says a cross edge cant go from lower vertex to higher vertex but in the diagram he has drawn the edge from 4 to 8 . Can any one explain how ?

[@abhishekpundir575]

I think what he means is that cross edge can't go from a lower to higher vertex based upon their starting and finishing time , like we can't have cross edge from vertex 2 to 4 because if we would have such an edge then we would discover 4 using 2 rather than going back to 1 and then going to 4.

[@sudheerays9559]

by higher vertex he means ancestor and by lower vertex he means descendant, 8 is not ancestor of 4 ....

[@CrackingTheGames]

Think of a cross edge as an edge connecting siblings in the tree

[@ritwik121]

kzbin.info/www/bejne/iHWkYqF9qKqJgrs -> here is the updated video by the same professor.... he explained ur confussion clearly in the updated video. He was basically saying - A edge from node 'u' to node 'v' can be marked as a cross edge if both the vertices dont share a ancestor descendant relationship and also node 'v' 's starting time should be more than node 'u' 's finishing time.

[@curious_banda]

He says higher number, not vertex. By number, he means DFS number. Since DFS number are chronological, thus if Y has higher DFS number than X, Y was encountered later than X. Thus, only a cross edge Y->X can exist. If an edge X->Y exists, Y will be explored while exploring X, and thus would become a child.