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

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 ?
in Algorithms by Active (1.2k points) | 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 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.

by Loyal (5.3k points)
edited by
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$

 

wiki link : here

0

@ how EB is cross edge in your original answer?

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

Watch video of this comment it will clear all your doubts--https://gateoverflow.in/235758/breadth-first-search?show=284709#c284709

0

Thanks @ brother!

0

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

0

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

0
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
50,647 questions
56,497 answers
195,494 comments
100,826 users