retagged by
2,275 views
1 votes
1 votes
True / False?

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

2. The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.
retagged by

1 Answer

1 votes
1 votes

Both Statement are correct.

The below Image shows a Graph G and BFS is applied on G. and a back edge that shows a cycle.

Related questions

1 votes
1 votes
1 answer
1
rahul sharma 5 asked Oct 4, 2017
645 views
If in a given graph all edge weights are equal and negative then BFS will correctly find out single source shortest path to all vertices,starting from vertex v? True/Fals...
0 votes
0 votes
0 answers
2
1 votes
1 votes
1 answer
4
dileswar sahu asked Sep 2, 2017
2,151 views
The depth of any DFS (Depth First Search) tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.I think in line graph has the...