DFS back edge

Xylene asked Aug 20, 2017

2,496 views

0 votes

If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?

Programming in C
depth-first-search
algorithms
graph-algorithms

+ –

Xylene asked Aug 20, 2017

Xylene

2.5k views

See all

1 1 comment

Rishabh Gupta 2

commented Aug 24, 2017

True.

1 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

Best answer

4 votes

I hope it is clear.

Anmol_Binani answered Nov 7, 2017 • selected Nov 9, 2017 by Xylene

Anmol_Binani

See all

7 7 Comments

Show 4 previous comments

Shubhanshu

commented Nov 9, 2017

Then also we have cycle a->b->c->a

0 votes

Xylene

commented Nov 9, 2017

Bro, read the solution properly. It's correct.

0 votes

Anmol_Binani

commented Nov 9, 2017

@ Xylene Welcome.! :)

0 votes

Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

6 votes

1 answer

MIRIYALA JEEVAN KUMA asked Jan 27, 2018

13,362 views

Back edge,tree edge,forward edges in BFS
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed ... back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements

Consider the following statements:1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff i...

MIRIYALA JEEVAN KUMA

13.4k views

MIRIYALA JEEVAN KUMA asked Jan 27, 2018

DS
algorithms
breadth-first-search
depth-first-search
graph-algorithms
programming-in-c
data-structures

+ –

1 votes

0 answers

Markzuck asked Dec 30, 2018

1,422 views

BFS and DFS - types of edges
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.

Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs?Individual meaning of BACK, FRONT and CROSS edges...

Markzuck

1.4k views

Markzuck asked Dec 30, 2018

Algorithms
depth-first-search
breadth-first-search
algorithms
graph-algorithms

+ –

0 votes

1 answer

Shivam Kasat asked Dec 9, 2018

444 views

which DFS algorithm to follow?
there are multiple algorithm of DFS available and i cant figure out which one to follow for solving question asking for the nodes which aren't pushed into the stack or the nodes which are pushed more than once, Tried to figure out from ... , https://gateoverflow.in/98484/dfs-using-stack https://gateoverflow.in/161225/dfs-number-of-nodes-not-pushed-into-the-stack

there are multiple algorithm of DFS available and i cant figure out which one to follow for solving question asking for the nodes which aren’t pushed into the stack or ...

Shivam Kasat

444 views

Shivam Kasat asked Dec 9, 2018

Algorithms
depth-first-search
algorithms
graph-algorithms

+ –

0 votes

0 answers

Lakshman Bhaiya asked Nov 13, 2018

841 views

Depth First Search (DFS)
Consider the following sequence of nodes for the undirected graph given below$:$ $(1)PQSTWVUR$ $(2)PQRSTUWV$ $(3)PQRTUSVW$ A Depth First Search (DFS) is started at node $P.$The nodes are listed in the order they are first visited. Which all of the above are possible outputs$?$ $A)Only (2)$ $B)(1) and (2)$ $C)(2) and (3)$ $D)(1) and (2)$

Consider the following sequence of nodes for the undirected graph given below$:$$(1)PQSTWVUR$$(2)PQRSTUWV$$(3)PQRTUSVW$A Depth First Search (DFS) is started at node $P.$T...

Lakshman Bhaiya

841 views

Lakshman Bhaiya asked Nov 13, 2018

Algorithms
algorithms
graph-algorithms
depth-first-search

+ –

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

1 1 comment reply

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

7 7 Comments reply

Please log in or register to add a comment.

Related questions

1 1 comment

7 7 Comments