0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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).

I hope it's clear for you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.