# Question on Breadth First Search.

Let us assume there is a directed graph $A\to B \to C \to D \to A$. Now won't the Breath First Search tree contain a back edge but everywhere it states a Breath First Search tree can't contain a back edge. But in the case I've given there would be a back edge.

• That graph contains a cycle, so it isn't a tree. Also, I think you mean "breadth", not "breath".
– MPW
Apr 1, 2015 at 1:43

In Breadth-first search algorithm, each time you visit a state you mark it as visited. Hence in your graph, assuming you start from $A$ the algorithm will mark $A$ them move to $B$ and so on. When reaching $D$, it will look at $A$ but since it's already marked it will do nothing and hence stop since there is nothing else to do.
The Breadth-first search tree obtained is thus $A-> B->C->D$ (with no back edge).