Saturday 29 September 2018

Algorithms | Why DFS is used to find the cycle in the graph?

1. DFS is easier to implement.

2. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to also print the found cycle. This makes DFS a lot more convenient.

BFS won’t work for a directed graph to finding cycles.

Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the paths that B is visited. When continuing to travel the next path it will say that marked node B has been again found, hence, a cycle is there. Clearly, there is no cycle here.



Related Posts Plugin for WordPress, Blogger...