160 views
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?

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 ?
| 160 views
0

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

+1 vote

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.

by Loyal (5.3k points)
edited
0
Thanks :)
0

@Sandy Sharma by mistake i gave you a wrong example, now i have corrected it. If it answer all your queries and is correct you can select it as the answer.

0

@ plz explain back edge and cross edge definitions...I don't know anything about it

0

@himgta

Back edge : Edge $(u,v)$ in the tree traversal in which $v$ is the ancestor of $u$

Forward edge : Edge $(u,v)$ in the tree traversal in which $v$ is one of the descendants of $u$

Cross edge : Edge $(u,v)$ in the tree traversal in which $v$ is neither the ancestor not the descendant of $u$ 0

0
$B$ is not the ancestor of $E$
0
plz define define ancestor and descendant as well!
0

See this

0
I m still confused...can u plz list out all the ancestors or descendants of nodes given in the tree of your answer!
+1

0

Thanks @ brother!

0

@Shobhit Joshi As you said

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

0

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

0
yes, you'r right . Thanks .:)