BFS problem

Question

True or False , with reason.

For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic?

Answer is False

Explanation:

FALSE. It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level)

 

Can someone explain it ?

Comments

If you have doubt regarding tree edge, back edge , cross edge then you can see Here

Some good questions like this are--

https://gateoverflow.in/200370/back-edge-tree-edge-forward-edges-in-bfs

https://gateoverflow.in/4774/dfs-cross-edges-forward-edge-and-back-edges

Answer 1

Back Edge : an edge that connects a vertex to a vertex that is it's ancestor.

 

Start the $BFS$ from vertex $A$ then you take : $AB,AC,AD$, they are tree edges.

Now you take $BC$ it is a cross edge, then $CD$ it is also a cross edge then $DE$ this is a tree edge.

Then you can take $EB$ this is a cross edge.

So, there are no back edges but still a cycle $EBCD$ exists.

Comments

@Shobhit Joshi As you said
After taking AB,AC,ADAB,AC,AD, they as tree edges.

How can we take take BC , as C will already be visited node.

---

@Sandy Sharma that's why i said it is a cross edge not a tree edge

---

yes, you'r right . Thanks .:)