what about forward edge ? we can make cycle with na ...... backedge is sufficent but not necessary

The Gateway to Computer Science Excellence

0 votes

**Which of the following statement is true?**

- For a directed graph, the absence of back edges in a DFS tree can have cycle.
- If all edge in a graph have distinct weight then the shortest path between two vertices is unique.
- The depth of any DFS (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex.
- Both (a) and (c)

+1 vote

I think the correct answer is option c.

Because if a DFS traversal graph consists of a back edge then it has a cycle. and option a is mentioning just the opposite.

And 2 paths can have the same length like 7+3=10 and 6+4=10.

Because if a DFS traversal graph consists of a back edge then it has a cycle. and option a is mentioning just the opposite.

And 2 paths can have the same length like 7+3=10 and 6+4=10.

0 votes

1. A directed graph can have cycle only when it has back edge in DFS tree. So it is FALSE.

2. The distance between two vertices may be same using the different paths. Also, no of edges in those paths may vary. So this statement is also FALSE.

3. BFS distance from source is the minimum number of edges to reach the target node. In DFS, the depth of any node will surely be greater than or equal to minimum number of edges from the source. Hence, this statement is TRUE.

2. The distance between two vertices may be same using the different paths. Also, no of edges in those paths may vary. So this statement is also FALSE.

3. BFS distance from source is the minimum number of edges to reach the target node. In DFS, the depth of any node will surely be greater than or equal to minimum number of edges from the source. Hence, this statement is TRUE.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,616 answers

195,897 comments

102,357 users