Question Details

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Options

A

A DFS tree of G is a Shortest Path tree of G.

B

Every non-tree edge of G with respect to a DFS tree is a forward/back edge.

C

If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.

D

Both BFS and DFS can be used to find the connected components of G.

Show Answer
Correct Answer
B Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
C If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.
D Both BFS and DFS can be used to find the connected components of G.

Solution :

The correct statements are:
1. Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
2. If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.
3. Both BFS and DFS can be used to find the connected components of G.

Let us analyze each statement step-by-step to understand why they are true or false:

Statement 1: A DFS tree of G is a Shortest Path tree of G. (FALSE)
Depth First Search (DFS) explores as deep as possible along each branch before backtracking. It does not guarantee finding the shortest path (in terms of the number of edges) from the source to other vertices. In contrast, Breadth First Search (BFS) is specifically designed to find the shortest path tree in an unweighted graph. For example, in a cycle graph of three vertices A-B-C-A, starting DFS at A might yield the path A-B-C, making the distance from A to C equal to 2, whereas the shortest path is direct from A to C with a distance of 1.

Statement 2: Every non-tree edge of G with respect to a DFS tree is a forward/back edge. (TRUE)
In an undirected graph, when we perform a Depth First Search, the edges of the graph are classified into two categories: tree edges (edges in the DFS forest) and back edges (non-tree edges that connect a vertex to an ancestor in the DFS tree). Under undirected DFS, there are no cross edges or forward edges that are not ancestors/descendants. Since the graph is undirected, a back edge and a forward edge are structurally the same (just viewed from different endpoints), so every non-tree edge is a back edge (which can also be referred to as a forward/back edge). Thus, this statement is true.

Statement 3: If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other. (TRUE)
In a Breadth First Search on an undirected graph, vertices are discovered in layers based on their shortest-path distance from the source vertex s. Let d(s,x) denote the shortest distance from s to x.
For any edge (u,v) in an undirected graph G, the distance of the endpoints from the source can differ by at most 1. That is:
|d(s,u)-d(s,v)|≤1
This inequality holds for all edges in the graph, whether they are tree edges or non-tree edges. Therefore, if (u,v) is a non-tree edge, the distances from the source s to u and v must satisfy:
d(s,u)-d(s,v)∈{-1,0,1}
which means the distances are within ±1 of each other. Hence, this statement is true.

Statement 4: Both BFS and DFS can be used to find the connected components of G. (TRUE)
A single execution of BFS or DFS starting from a vertex will visit all vertices in its connected component. By wrapping the search in a loop that iterates through all vertices and starts a new BFS or DFS traversal whenever an unvisited vertex is encountered, we can systematically discover and label all connected components of an undirected graph. Thus, both algorithms are widely used for this purpose, making this statement true.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: