When doing BFS, you will find the cycle while developing only O(B^d)
nodes, where B
is the branch factor and d
is the size of the cycle + header from the source to it. (the length of the cycle if the source of the BFS is in the cycle).
DFS cannot guarantee you this, and might discover the entire graph before finding the cycle.