The Gateway to Computer Science Excellence
0 votes
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


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 ?
in Algorithms by | 234 views

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

Some good questions like this are--

1 Answer

+1 vote
Best answer

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.

edited by
Thanks :)

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


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



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$


wiki link : here


@ how EB is cross edge in your original answer?

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

See this

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

Watch video of this comment it will clear all your doubts--


Thanks @ brother!


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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,483 answers
95,287 users